From the Super Mario Wiki
Mario's Shoes are a part of Mario's clothing. They are brown in most games and don't seem to have neither laces nor velcro. They have yellow soles. Mario almost always wears these, even when he swims.
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.