UPDATE FEB 2012: This guide is featured on Adafruit's blog
This is Faz3a II, my first line-following robot, which I also hope to use for maze-solving. I used the Arduino Uno, Adafruit motor shield, Pololu's QTR-8RC line sensors and motors. You can build a cheaper and lighter version of this robot using the Atmel Atmega328 and the L293D h-bridge. This robot weighs about 300gm and costs about $90 USD.
For my previous robot projects, I used an empty external hard disk enclosure as the robot platform. But for this robot, I am using a DVD case. All in all, I found the round shape of the DVD case a better choice for maneuverability. Not to mention the low cost of DVD cases and ease of stacking layers to hold more parts, with the help of long screws and nuts.
For this project, my task was simplified by the availability of software libraries from Pololu and Adafruit for the sensor and motor shield respectively.
Of course I could have bought a robot kit but I want to be able to take my robot apart anytime to build another one or use the parts in a different project. So if your passion is robotics, consider getting a ready robot kit.