I've been wondering how much one can do for $50. The question is, can you build an *interesting* robot for that kind of money? I have a $10 HEXBUG that is cool and a marvel in its own right but it doesn't do much.

Anyway, if you can find a Basic Stamp on ebay for $25 or so then maybe. But the BS2 won't read voltages, so you need to convert to frequency or use external ADC ($2-10?). Or get an I2C sharp ranger for $11 or so (similar cost for normal rangers).
Probably the cheap way to go with MCUs is to get an AVR and build the board yourself. I saw an article on building a simple Arduino board here:
http://tinkerlog.com/2008/01/07/arduino-on-a-prototype-board/ (components run 4.50euro which would be what, about $10 US?) The AVR programming tools are free/open source.
If the budget is a little higher, you could look at Pololu's Baby Orangutan + programmer combos ($40-50, includes motor controller), or real Arduino (stamp $40 or usb $35) e.g., from Sparkfun...
Michael