What happens is that, as the image is decoded, it is mapped to the existing "locked" pens, that is, the ones Workbench is already using and the ones in the palette editor. Any colours other than those it needs are taken from the remaining unlocked pens, which are altered to suit and then locked. The precision of these mappings can be adjusted, poor precision will leave more pens free for other purposes, but doesn't look as good. I should ask here, what version of the OS are you using? Because 3.9 has much better options for the background than 3.1.
As for image formats, anything you have a datatype for you can use, but I strongly suggest IFF as it doesn't need any translation. Scaling the image to your screen resolution and pre-mapping the colours will greatly reduce the time taken to display the image. Photoshop does export IFF IIRC, but I recommend Personal Paint for these things, since it's so much better suited to dealing with indexed colours, and can remap, resize and dither easily for the best results.
100% agree with this: I use ImageFX to scale and map to my WB palette... but even some freeware apps. can do it, iirc...
Personal Paint IS great.... but I found ImageFX easier to re-map WB pics... tho, I am running in 64 colors... dang, I SO NEED a gfx. card!!
Ohh, DON"T count on Photoshop to handle ALL ILBM's (Interleaved BitMaps, the proper term) ... EHB, Dynanic Hires, etc. may well not work...