Mario's Shoe
Mario's Shoes are a part of Mario's clothing. They are brown in most games, and seem not to have laces of any kind. They have yellow soles.
In Luigi's Mansion, Mario's Shoes are one of the five items Luigi needs to take to Madame Clairvoya to find him. It is found in the Twin's Room.
In the Paper Mario series, Mario changes his shoes to a pair of either green or blue boots, (called Super Boots), and then later to a pair of red boots, (called Ultra Boots). The boots are more powerful than Mario's standard boots, and as such, grant him extra abilities and increase the power of his jump attack.
In the Mario & Luigi series the players can change the shoes which gives them different abilities. See Clothing for more details.
Trivia
In the Cloud Mario artwork of Super Mario Galaxy 2, is seen that Mario uses boots with two red cords.
