Get XWE, save the sprites from Sonic.plr to any folder, recolor them, put them in a new wad, choose abilities and stuff, test, release, get flamed.
There, the progress of a recolor. Really, you'd have to make a really good recolor to get respect for it. That means, make sure the recolor doesn't make the game too easy, try to show as many customized parts as possible, and maybe even a custom style for the sprites. But not a Sonic with automaticly the color purple(by setting prefcolor to purple) and yellow eyes, thanks.