Alternate costumes:
At the main menu, press Up, Up, Right, Left, Down, Down, Start. Then, enter the game, go to a save point, and press the 'Skin' button.

Original costumes:
Beat the game.

Thanks to Revolution readers Alex Jackson, and Summersby!