Not to hijack this topic, but I feel a bit of elaboration should be made to show the newbies about proper shading, how to do reference colors (IE, based on other characters) and the like.  I was about to type one up myself, but I don't want to seem like I'm...ahem....pissing on anyone's lawn. 

Shading in the KOF style is supposed to be done through the Gradient technique. This requires that each color has anywhere from 4 to 6 shades and each of them with a considerable amount of contrast between one another.

One of the rules of Gradient is that 2 shades of a color that aren't directly neighbors to each other shouldn't touch at all, there must be at least a single pixel line in between one another. There are certain exceptions used mostly on newer sprites for really contrasting shadows, but usage should be minimum.

If you were to pick your shades from the gradient map on the left, each color should be at least 3 areas away from each other, and the lightest shade should be very bright, since the highlights are exactly what gives that crisp look to KOF styled sprites. Of course it's always recommended that you use already existing palettes in order for you not to mess up shades lacking contrast - there's no shame in using what already exists!

Colorizing effects is generally done easiest by desaturating the image and then using hue/saturation to colorize it. In Photoshop, this is done by first going to Image→Adjustments→Desaturate and then Image→Adjustments→Hue/saturation, making sure to check the "Colorize" box.