I used Photoshop for it, but I'm sure there are other programs that can do the same.
How I personally manage my palettes:
1) Create a sprite using only a few shades of each color, smaller areas needing less. The shades can be handpicked or copied from a sprite that has a nice palette.
2) When drawing another thing, check if you can use those colors from your earlier sprite if possible.
3) Unless you are working with strict palette limitations (e.g. imitating a specific style), don't be afraid to add a middle shade to smooth things out a bit! Add as few as you can though.
^Here I added one shade between the two in an attempt to make the transition nicer looking^
4) This one's just a reminder of step two, but try to keep your colors multi-purpose. If you have a color you're only using for a small part on a single character, it should be easily replaceable.
When creating something like a large pixel scene, you can use some of the same techniques. The color count becomes even more important so you need to pay extra attention.