There have been some very good robots made from paper and cardboard on this site.
Use the search bar at the top to look for key words like paper and beam for inspiration.
Well picaxe is a good start. However if you want to make robots out of old toys and what not I would reccomend this book. http://www.amazon.com/JunkBots-Bugbots-Bots-Wheels-Technology/dp/0072226013
This is how I got into robotics. Very straight foreward easy to follow instructions to build beam robots.
Find old printers for motors, gears and stuff, get old cdrom drives for nice dc motors and maybe drivers ... oh yeah and floppy drives
You still need some brains, either go the BEAM way, or get some cheap microcontroller like Attiny2313 or pic16f628. Or a picaxe but I do not know them very well to recommend.