It can really depend on what you're going for, most of the time you can just go with using Photoshop's indexed color table to change large amounts of pixels at a time, but with some specific things (like when one color represents a lot of the sprite, but you only want part of it colored a certain way), you'll be doing sprite-by-sprite. I've done a lot of both, either is fine, really.