Also I guess step 0 would be firing up a media player. 8)

• First, you'll want to go through all the sprites of the character, noting the number of shades per piece that you're separating.  There's nothing worse than getting about 200 sprites in and noticing an extra shade to add.  This will give you an idea of how many colors you'll need to add to the palette.
• Next, you'll want to make your new palette with all the new colors you're adding.  I prefer to use Fighter Factory for this, but any program should suffice.
  
  As you can see, I have highlighted the 13 new sections I'll be using to separate all the different parts.  (Once again, make sure you go through the entire spritesheet and ensure you have all the shades accounted for.)
• Next, you'll want to add your new palette to all of your images.  The easiest way to do this is by batch automation within Photoshop.  Make sure all of your sprites are in their own folder, then create a new Action in which you add the new palette to one of your images.  (If your sprites look misshapen in PS, you may need to set the Pixel Aspect Ratio to "Square."  This can also be automated.)  Now, go to File > Automate > Batch.  Set the "Action" to the one you just created, then point it to the folder containing all of your sprites.  Finally, choose a folder to save them to then OK and let it do all the work.  Once complete, all of your sprites should have the new palette applied.  To check this, go to Image > Mode > Color Table.
• Now comes the fun part.  I like to have a palette template on my workspace, which makes it easy to grab your colors. (make sure this image is indexed with the correct palette too!)
  
  Using the Lasso tool, outline the section you want to separate.  This can be extremely tedious, but once you get the hang of it, it gets easier.  Once you have your piece outlined, use the Bucket tool to fill in with your new colors.   
• With the Bucket tool selected, holding ALT will bring up the Eyedropper tool, which makes it easy to grab your colors from your template.  Note that when you have something selected, you can "paint" another part of the sprite that is not selected to help you ensure that you have the right shade.  This is helpful on sections that are bunched up together, making it harder to differentiate the correct shade.
• Another helpful tip is using the SHIFT and ALT keys when making your outlines with the Lasso tool.  SHIFT will allow you to add to your outline, even if it isn't connected to your original outline.
  
  ALT will allow you to remove part of your outline, which helps alleviate mistakes you may make.
• Your finished sprite should have all visible sections recolored.
  
  
• I like to add each finished sprite back in to the character once it's complete using FF.  I do this because it is easier to flip back and forth through the sprites to check for mistakes.  The key is consistency, as you may have to make some adjustments and guesses when doing an entire spritesheet.  I had to do this alot with Felicia's sprites, and remaining consistent was one of the hardest parts of her separation.
• Now you just have to repeat this process another 400 times and you'll be done.  Fire up some music and grab some beer, cause you'll be here for a while.