it is usually good practice to work with a reduced set of colors. It is usually easier to add in-between than to clean-up duplicates / close colors.
As for "which palette to chose", it completely depends on the scene you want to render. E.g. dramatic vs. dark vs. cheerful vs. quiet won't use the same colors. You may want to start with the colors featured in e.g. Arne or NES palette if you don't know where to start with. You could also look for the Open Platformer Project (or something similar with other game genre) and reuse someone else's palette until you've grown more comfident about your color picker skills.
(I deliberately skip about how *I* pick my colours, because I don't have a good process so far)