The other day I saw that there is a Super Mario Competition for a conference in September 2009. I decided that this was a fun project to hone my AI programming skills and started to write a little path planning AI, using A*. The source code for this can also be found on this page.
Update (6. Sept 09): My Mario AI has won both Mario competitions this year, the ICE-GIC conference held at Imperial College in July and the IEEE Computational Intelligence in Games symposium in Milan in September! It was a really close decision between the first three solutions though (all of which are using A*). Yay!
Source code here: https://github.com/RobinB/mario-astar-robinbaumgarten (it's not very clean …)