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.
