All sprites are 12 colors to my knowledge. You're in for a fun time, because you'll need to learn a bit of sprite assembly. However, it's probably possible to carefully place the new character's subtiles such that the old character's sprite assembly will work for you.
I think
this thread provides a fairly comprehensive overview of sprite assembly. Man, I want to write a guide that details sprite animation, but I won't get to it for awhile. Vehek or justin3009 probably have info on that lying around somewhere though.
As far as insertion, it's literally as easy as copying and pasting from a source image to the ROM and then taking care of the palette, but you'll have to use Temporal Flux to compress the graphics if you're editing NPC or enemy sprites.