I'd assume... a lot of work and some sprite editing or normal editing program. Can't really give you any more help than that. I've wanted to do this myself, but sprite editing on that level is a fine and time consuming art. There were quite a few tutorials running around and you may be better off searching some MUGEN sites or something dealing more just sprites.
Which are you after, pixel-manipulating art or full-on MUGEN animated sprite characters? If it's the former I'm your man. Just ask these ladies.
"Take the Yuan-Ti, bash them with a club made of frozen stupidity, then rip out their sense of subtlety with a rusty spoon, and then you have the Snakes of Mercy Isle" -Taltha Widowfang, drow stalker
Now playing at an MA near you: Dragonslayers #335375
Hehe Kat and Rowr look like they came straight out of Street Fighter or something!
Anyone know how to make custome MUGEN characters?