I'd like to add that you can also use "Sprite Explorer" which is a little more user friendly. Why? Because it'll accept anything, 256 color bitmap or not. Sure it'll affect your colors, but you can still see its animation.
In order to make things into 256 color bitmaps without reducing color detail, don't use MSpaint. Adope Photoshop is your best bet. You may not lose much color detail if you save it as a 256 color bitmaps in MSpaint, but every time I did it, all the detail was lost. So Photoshop is my preference. I'm sure Jasc Paintshop Pro will work fine as well.
To save as a bitmap with 256 colors in Photoshop, do the following.
1) Select your current picture (make sure its 256x256 maximum. anything else is too big for a sprite)
2) Go to the top and select the IMAGE tab.
3) Scroll down and select MODE
4) Scroll down and select INDEXED COLOR
this will handle the job nicely, though as indexed color, you can do only minimal changes to the picture, so if you wish to make it alterable again, then do steaps 1-3 again, and choose RGB color. Then when you're sure all the alterations are complete, make it Indexed color again. Now, simply save as a bitmap and you're done.