How can I add new colors to Samus, while also having the character selection screen show me the color and the Samus face appearing during the match by the damage percentage?
You need to replace some specific images in your sc_selcharacter.pac
Sadly I don't remember them. I suggest you downloading a popular Mewtwo hack, there you see where something is replaced. Then you know where to replace what. (Mind the image sizes!)
Also, do I need to account for Zero Suit Samus Final Smash while doing this? How?
I don't think so.
And lastly, I cannot simply replace any stage with any other, they have to be very specific stages that can take over others, am I right? Say, I cannot put a stage that's labeled under FD over Norfair, or can I?
No, with Rel files it is possible to port any stage over another (there are 2 exceptions i think).
maybe this link helps you:
http://www.lakora.us/rel/base rel = where the stage originally goes over (open the stage with brawlbox, then you should see the stagename)
to replace = the stage which you want to replace.
you will get a rel to download. simply put it into your module folder
Edit #1: Those exceptions are Lylat Cruise and Castle Siege.