Alternate costume (SSB)

Mario's palette swaps in SSB

Yellow: Based on the yellow-and-purple outfit of his rival, Wario.
Blue: A red/blue reversal of his traditional colors. This is seen as a partial reference to Mario's varying appearances in games prior to Nintendo's officially establishment of Mario's outfit of consisting of a red shirt, blue overalls and red hat. In various earlier games, Mario occasionally also appeared with sometimes a blue hat, red shirt with blue overalls or a red hat, blue shirt with red overalls. However, this particular combination of a blue hat, blue shirt, with red overalls was never used in any game.
Brown: A reference to Foreman Spike from Wrecking Crew.
Green*: The color inverse of his traditional colors. Contrary to popular belief it is not a reference to Luigi. However, it does coincidentally resemble Luigi's colors from the arcade version of Mario Bros.

Yoshi's palette swaps in SSB

All of Yoshi's costumes are the different variations of the Yoshi species from the various Yoshi games including:

Captain Falcon's palette swaps in SSB

Kirby's palette swaps in SSB

Yellow: The same as Keeby. It is also similar to his colors scheme when he is Beam Kirby, sans the hat.
Red: The same as when he is Fire Kirby, sans the hat.
Blue: The same as when he is Ice Kirby, sans the hat.
Green*

Samus's palette swaps in SSB

Pink: Based off the appearance of the Varia Suit when missiles are selected in the original NES Metroid game. It is also the color of the Gravity Suit in iterations prior to Metroid Prime.
Green
Brown
Blue*