I found this a while ago and thought it's worth mentioning. Secret Maryo Chronicles is a Mario-Clone and seems to be one of the better ones. It's in a quite early stage, but with some talented level designers it could evolve to something really nice.
The gameplay is a bit different from the original games, it doesn't have a speedup-button. It's features are comparable to Super Mario Bros, while it's graphics are more like Super Mario World.
It's free software and it's available for Windows and Linux.