From the Super Mario Wiki
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 Twin's Room. 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.