In addition to Cure's and DawnBringer's excellent posts, also be aware that color reduction algorithms normally weight the importance of an area of the colorspace by the number of pixels falling into that area. So, if some sprites' colors are more important than others, you can scale them up on the 'import sheet' to give their colors more priority in the final palette.
Once you have a palette generated, there are plenty of options for converting your RGB sprite work to it. There are batch processors specifically for this task; you can also use something like GIMP, where you can import the sprites and then convert them to your predefined palette using Image->Mode->Indexed.
An alternative approach to generating a palette would probably use DawnBringer's 'Fill colorcube' or 'Expand colors' scripts (for GrafX2 -- is a separate package that needs to be installed, though.). You would pick out some 'key colors' that definitely needed to be in the palette, and maybe some 'peripheral' colors so the palette has good coverage of the RGB gamut... maybe you would get to having 32 or 48 colors. Then use one of the above two functions to automatically fill in the largest 'gaps' in your palette (which one, is a matter of experimentation I've found.). The result being a palette of however many colors you specify (128? 256?).
