In highschool we had a class where the teacher would provide LEGO Mindstorms for us and let us do anything we wanted with it. Using optic sensors, we made it find its way out of a maze which we set out on the floor with tape. These things are great fun, but probably most suitable for kids to play with.

Probably a better idea would be to get started with something like an Arduino. Not too long ago I read about Tessel on HN which seemed interesting, sort of an Arduino but you could program it with JavaScript, if that's your thing.

Also there's tons of articles and videos on the web of fun projects people built with Arduino's and Mindstorms, so I would definitely google around a bit to see if you find something you think is interesting. Anyway, good luck.

To add to what jeremyaarts said, last year Lego released an upgraded version of their Mindstorms set called EV3. I know there was a board that allowed you to enhance the older NXT Mindstorms set with an Arduino, though I'm not sure if this board is compatible with the EV3. One of the nice things about the EV3 is that it runs it's own version of linux, however you can also can run a custom version of linux on the EV3 if you want, opening the system up to a world of fun :-)

Arduino robot hacking is a great place to start.

An alternative or complementary approach is to work in simulation, and with that decision you can immediately start working with state of the art stuff, as follows:

ROS is the dominant Open Source robot platform. It works with the powerful Gazebo simulator. It's all free. Researchers, companies, universities, and hobbyists all use it, and there's an active community. The learning curve can be steep, but this is powerful stuff.

http://www.ros.org/

For a simpler start, take a look at the platform that was popular before ROS overtook it: Player/Stage

http://playerstage.org

reddit.com/r/arduino

robots.net

http://www.societyofrobots.com/robotforum/

shoot me an email if you want to talk robots.

check out instructables.com. search on arduino it's a micro controller. I've been thinking about popcicle sticks and mini servos. both are really cheap.