Pololu has a lot of nice stuff for beginning robotics, and those parts look fine. You don't really
need encoders at the start, but can always wire them up after things are off and running.
I've built 15 or more robots and never even used wheel encoders, as I like to control the robot
mainly from sensor input [sonars, Sharp IR rangers, photoresistors, bumpers, etc].
However, if you're just getting started, and can afford it, I might recommend the 3pi robot
instead. This will get you off and running really quickly, ie, you'll learn a lot more a whole lot
faster. Appears to be Arduino compatible too.
http://www.pololu.com/catalog/product/975Robotics involves knowledge in many more areas than most Arduino projects - ie, different types of
sensors, mechanical fab, motor control, general programming, plus robotics-specific programming - and
if you're not already knoweldgeable in a lot of these areas, you'll learn faster with something like the 3pi.