The brown was because of the 4-color limit. Like it was said, the 4th color being the transparent one. The brown was used because Green was used for the clothes, the peach for the skin, and the brown for the hair/boots/etc. Which would leave the white for the transparent background. They couldn't use a black, besides, Link's hair was brown.
Its kinda hard to explain ya know...
Edit: Lolz, I'm not very good at explaining things... D:
Heres an image to explain better.
You see the 4 color pallete? Thats what they used.
Brown: Hair Boots Ect.
Green: Clothes.
Peach: Skin
White: Transparent Background.
They also used the brown for the outlining, cause I mean, he doesn't look to good without it
1. What he looks like in game.
2. What he would have looked like without an outlining.
Yes Mario did. Look at the Super Smash Bros NES Banner
Thats because whoever made that banner put a black outline around him, probably to help him blend better.
Also which banner are you talking about anyways? o_O