I just did all 16x16 pixels and whatever colors I like. I try to keep the amount of colors to minimum like if you can do it well with 4 colors/sprite, then awesome! Some do require more, but I never use... I'd like to say more than 8, but definately no more than 10 colors/sprite. If there's a general palette to the game then they can just switch the colors of the sprite to those most closely matching the ones you had.
Really, I don't know why anyone would do that this day and age tho. PNG format is compact as hell and I only limit my colors for the artistic effect. They used to do it so they could use the minimum amount of RAM and disk space for the graphics.