Power: CR2450 size rechargeable lithium ion coin cell, 140mAh, 3.6V
Charging: MCP73831 charge controller, powered by USB (male usb plug printed right on PCB)
Locomotion: 2 pager vibrator type motors
Control: ATtiny85, programmed by an arduino and then inserted into socket.
Sensors: Only limited by your imagination. Photocells are one obvious starting point
Cost: Now that I have found a source for cheaper batteries (ebay! http://goo.gl/HYa7EU), the base robot without any sensors are about $9.80 per robot, plus shipping. Dirtypcbs.com ships for free, Mouser/Digikey/Newark do not (though they are most reasonable...10 tinybots worth of supplies costs $3 to $5 to ship in the US from Mouser). See below for details. Sensors would be another $1.00 or so depending on what you decide to add.
If this were scaled up to, say, a production run of 100 tinybots, the cost would come down to less than $6.50 per tinybot (again, not taking into account the cost of shipping parts from Mouser).
On the other hand, a number of these components are probably lying around your shop, and many of the rest could be obtained for free as samples, at least for a couple of robots' worth.
Current BOM: See Github repository (both csv and Excel formats), or the Mouser.com project page (http://goo.gl/kvc0AO). Note that the Mouser project page does not include the motors, PCB, or battery as these are not available from Mouser or are more expensive there (found a unique deal on ebay for great rechargeable coin cells, the motors are much cheaper if obtained through aliexpress.com, and obviously the PCB comes from the PCB house, in this case dirtypcbs.com)
PCB: And finally, here is what the next version of the board will look like. Actual size is 1.4 x 1.9 inches (3.5 x 4.8 cm).