From the Super Mario Wiki, the Mario encyclopedia
Mario's Shoe is an accessory or an item used for various purposes in the Mario franchise.
In Luigi's Mansion, it is one of the five items Luigi needs to take to Madame Clairvoya to find Mario. It is found in The Twins' Room during normal gameplay, and the Billiards Room in the 3DS version's Hidden Mansion. After giving it to her, she says: "Wh-what is this? If it isn't Mario's Shoe! Why, the sole is so worn, as if he's walked a thousand miles!"
In the Paper Mario series, Mario changes his shoes (called Boots) 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.
Luigi's Mansion (Nintendo 3DS)