Motors are a really big subject. I tried to simplify that part of it by getting an inexpensive kit from Tamiya. To drive them you need to send PWM output to an H-bridge, which supplies power to the motor. Arduino has PWM ouputs - 6 of them, of which you will use 4 to drive left forwards, left backwards, etc.
Picking an H-bridge is tough. If you use low voltage motors, you will need more current to get the same amount of work done. High voltage motors use less current. Exactly how much current you need at a given voltage for a given pair of motors is difficult to determine if you don't use a solution someone else has already worked out.
H-bridges also have varying degrees of availablility (some look great on paper, but you cant actually buy them anywhere!). They usually come in the form of an IC, although you can build your own out of discrete devices (bipolar transistors or MOSFETs with drivers) if you have mad EE skillz.
There is a thread going on now under Hardware Development regarding a motor shield for Arduino. If you pay attention to it, you may find that the shield will supply your H-bridge needs for a motor pair you have (or have in mind). I use kit motor driver pcbs built around the L298 chip.
Wheel encoders are used to capture the speed with which either your wheels or your motor are spinning.
I have a pair, but I'm still learning how to use them. The goal is to take the actual speed that the drive is turning at and use feedback to adjust the PWM output from Arduino. This feedback loop makes it possible for differential drive robots to do what comes easily to some other drive systems - move in a straight line!