My first arduino project: what parts do I need to create the simplest vehicle?
If you just want to make a really simple robot you need a few things.


Motors
Power source 
Chassis 
Wheels
Microcontroller "The Brain"
Possiblly sensors?


I would start with something that has a chassis and motors already. Designing a drive train can be a daunting task just because of the ridiculous amount of variability and many unknowns. With that being said you can pick from many different types of robot bases from many different vendors. 

Here is a complete chassis from sparkfun that includes all the mounting hardware and motors. I bought it for a friend of mine who wanted to get started with robotics. Plenty of others exist if you don't like this one.

After find a chassis with motors you are going to need the brain (microcontroller). I would honestly just purchase the Arduino Uno to get started. 

After you get the brain you need to get a special chip that allows you to control external loads that would be too much for the Arduino's digital pins to handle. What you need is called a motor controller or h-bridge. This motor controller will work perfectly with the motors on the sparkfun chassis. Once you get that you can checkout this motor controller tutorial. As for a power supply for the Arduino and motors a simple 9v battery with DC jack will do the the trick.

Finally you want your robot to do something. A common "hello world" of robotics is to use some type of distance sensor on your robot. Sparkfun has a bunch of different sensors to choose from. Depending on what you want your robot to react to will determine which sensor you need. 

If you get stuck along the way or need inspiration make sure to check out the Let's Make Robots website!