Don't use it personally, but there's an on-line
generator that resizes images automatically for you.
The size is 600 x 800 pixels, as you said. In my experience, the images needs to be in 'portrait' orientation, otherwise the Kindle will try to display it the wrong way around. The Kindle will handle .JPG and .PNG files. PNG is a less 'lossy' file format, so I always think it's preferable.
Should be 16 colour channels. I don't tend to bother changing this within PhotoShop, and just send pictures to the device that have millions of shades: - as long as the image is bold and doesn't have too many subtle colour-gradations, I find it tends to turn out alright. Experimenting with the brightness/contrast and highlights/shadows settings to make the most of the Pearl screen leads to bold images that really pop off the screen.
This thread on KindleBoards is good for getting ideas for what kind of images tend to work well.