Well, I said "for most of it". For recoloring I pick out a few palettes I think might work, then use the Erase tool to replace the shades on the sprite one-by-one. If a palette works well, I'll set the recolored sprite aside; if it doesn't, I just delete the sprite. Once I've tried all of the palettes I picked out, I'll put the recolored sprites side-by-side to pick the best one.
...Then I'll usually need to pick a palette for a different part of the sprite.