Although the thought of such a project may seem complex, when you break it down into small parts it is quite easy. This is exactly what Instructables user Angelo ASCAS has done with his Arduino-powered tank robot. By using a large chassis and tank track system there's plenty of room for expansion as well, including an IP camera that broadcasts live images back to a PC and larger batteries for extended run time.
The remote control is via a custom Android app however it's just sending serial commands over a Bluetooth link so you can either create your own Android App or a hardware-based solution with another Arduino. The results of this project are excellent and shown in the following video:
If you're looking into starting with Arduino and robotics, such as controlling a stepper motor (or DC motors) from your Arduino or compatible, check out our new HBRIDGE: DC/stepper motor shield. Based around the powerful Allegro A4954 H-bridge driver IC you can control two DC motors with complete ease, or one bipolar stepper motor. With connections for external power management, a complete beginners' guide and documentation - motor control couldn't be any easier. For more information and to order, visit the HBRIDGE: page.