Mario's Cap is an important part of Mario's clothing. The hat is red and has Mario's "M" symbol. This hat has appeared in nearly every game featuring Mario. Mario has worn the same hat since he was a baby.
Mario was given his hat in his first appearance in Donkey Kong because of the limited advances in video game graphics when the game was made. A red cap was added because programmers found it difficult to create the hair movement that would occur when the character jumped.
The hat has appeared with Mario ever since then, but was unimportant until Super Mario 64 which the first game in which Mario can lose his hat. When the hat is lost (by having it stolen by an Ukiki or Klepto or blown off by a gust of wind), Mario takes more damage when attacked. The same happened in Mario's next platformer, Super Mario Sunshine, but with the added effect of gradually losing health due to the heat. Even if hatless Mario finds some shade and gets under it, it is still possible for him to take damage from the heat of the sun. The only enemies that steal Mario's cap are Swipin' Stus.
In the remake of Super Mario 64, Super Mario 64 DS, Toad revealed that the cap that Mario wears is special and if were to get blown off of Mario, he would have nothing but bad luck. As hinted in Super Mario 64 DS, Mario's hat may be a source of his strength. Mario's cap can also be found in most levels when playing as Yoshi. The cap will give the dinosaur the appearance and abilities of Mario (but retains his voice), until he gets hurt, finishes the level, or gets it stolen and loses the cap. Luigi and Wario can also pick up Mario's cap, and gets the same effects as when Yoshi picked up one. If Mario loses his cap, he can obtain it back by going back to the same level to find it. However, if he instead gets a star from another level, he can simply talk to Toad (who will find and wear Mario's cap) and get it back from him.
Courses Mario's Cap appears in even when he is locked:
Another sign of that cap's importance to Mario is at the end of Super Mario Galaxy 2, when the Baby Luma takes Mario's cap as a souvenir before returning to the Comet Observatory. Mario was shocked about losing his cap at that point. He is seen capless throughout the credits, but when he is playable again, he regains his hat somehow (possibly having another hat).
In Super Mario 64, Mario has four different types of hats: the Wing Cap (which enables Mario to fly), the Metal Cap (which enables Mario to walk underwater and to walk through fire), the Vanish Cap (which enables Mario to walk through certain walls) and his regular hat. While these powers were dispersed amongst Mario and his companions in Super Mario 64 DS, Mario's hat gained a new ability: when worn it could turn Luigi, Yoshi or Wario into Mario. If Mario loses his hat, he can't fly and use other caps or Power Flower abilities.
Additionally, due to certain glitches in Super Mario 64, Mario could end up with more than one hat, and could use the duplicate as an effective weapon. In Super Mario 64 DS, if someone wearing Mario's cap gets another hat, he instead gets an extra life. However, if the real Mario gets another one of his cap from a certain glitch in Snowman's Land, he'll pick up the cap and nothing will happen.
Also, when Mario gets almost any power-up, his cap will change color.