How do I replace an existing servo with a geared DC motor?
As you noted a motor on its own is usually a poor choice for driving wheels as it offers insufficient torque (but typically a higher rate of rotation). You therefore use a gear train to increase torque and decrease speed.

A servo is a geared motor with built-in feedback. Your servo package will have a controller, a position sensor (e.g. a potentiometer), the motor itself, and a gear train.

In a typical servo, the width of the pulse you send to the servo determines the position. The servo does not get its power from the microcontroller - you will note that the servo is plugged directly into your power rails (two wires - typically black/red), with only a signal wire (typically white or yellow) going to the microcontroller - which means that the microcontroller only needs to set the position, and not source the necessary current.

A servo that has been modified for continuous rotation will have the position sensor disconnected (and any mechanical stops removed). When your microcontroller specifies a position, the built-in controller will move the motor trying to reach the position. However, since the position sensor is disconnected, the motor never reaches the target position, and just keeps turning. A side effect of this is that instead of position control, you gain some degree of speed control. Typically, the servo's controller will change the speed of the motor depending on how far from the current position the target position is. As such, with the position sensor disconnected (and set to 0 degrees, for instance), if you ask for a small positive position, the controller will slowly move the motor forward, while a large positive position will result in a faster forward movement. (Likewise, negative positions, will result in a reverse movement).

A servo modified for continuous rotation can be plugged directly into your existing board, and will respond to the same PWM signals as your existing servos. As mentioned above, speed and torque are essentially inverses of each other, for a given motor. Common servos will have a rotational speed around 0.2s/60 degrees (50RPM), and a torque around 1kg*cm (meaning it would stall if you suspend a 1kg mass, horizontally, from a 1cm shaft). Using these numbers, you can get an idea of speed - however, you must keep in mind that rotational speed will decrease as torque increases (robot mass, wheel circumference, terrain/inclination, etc. will all increase the required torque). Under an idealized (no-load) scenario, 50RPM, on a 2.5cm diameter wheel (7.85cm circumference) will give you a speed just under 4m/min.

You can find servos that move faster, or that provide more torque (again, typically you have a trade off - more torque = slower speed for the same motor), but the price will increase quite quickly.

The other two types of motors you mention, don't have a built-in controller. This means that the signal going to the motor is not only controlling the motion, but also providing the current needed to drive the motor. Consequently, you can't directly control these motors from a microcontroller, as it is unable to source the necessary current. 

Typically an AVR is able to sink or source a maximum of 40mA per pin, with an absolute maximum of 200mA for the entire chip. It is, however, good practice to a) not exceed about 20mA per pin and b) ensure that whatever current you draw doesn't cause the chip to heat up excessively.

Since your AVR can't provide the needed current, you will have to use some form of motor controller - something that accepts a PWM signal from the AVR, and provides the needed current to the motor. In its simplest form this is a transistor array or a MOSFET. A darlington transistor array (e.g. ULN2003A) is common for simple control of small motors  (&lt;500mA), more complex control can be achieved using a chip such as L293(D), while slightly larger motors (&lt;2A) often use a specialized chip (e.g. L298N - which can control 2 motors, for a total of 4A continuous).

Firstly, consider a geared motor. It really is just a motor with a gear train - the faster the motor turns, the faster the output gear/shaft will turn; the greater the gear reduction, the more the increase in torque. 

In a traditional sense, the more voltage you apply to your motor, the more current you will draw, and the greater the speed and torque. However, a microcontroller can't change the voltage it outputs - it can output a 0 or a 1 - no voltage or maximum voltage. In order to control the speed therefore, you use pulse width modulation (PWM) - you send a signal that turns on and off fast enough that the momentum of the rotor keeps it spinning (but slowing down) until the next pulse briefly accelerates the rotor. The greater the proportion of the time your pulse is 'on' (called the duty-cycle), the greater the speed. (e.g. if you pulse a 5V signal at a 60% duty cycle it might approximate a 3V signal). 

In terms of the wiring, there is is some amount of similarity between a geared motor and a servo:


Servo signal: 20ms period, with 1 to 2ms pulse widths (interpreted into a position by the controller)
Motor signal: period varies widely (small motors and slow controllers work best with low frequencies - perhaps a few hundred Hz (a period around 2 to 10ms), while larger motors and controllers that can switch quickly, work well with higher frequencies (several 10s of kHz). The duty cycle determines the speed.
Servo wiring: power from rails (two wires), signal from micro controller (1 wire)
Motor wiring: signal from microcontroller (one wire) goes to motor controller which provides signal and current to the motor (two power wires would go here). 


So, you can still have your PWM signal going from the microcontroller to the motor controller, and the motor controller plugged into the rails and outputting to the servo. It is however, important to realize that controlling direction requires switching the polarity of your signal, which is typically done by your motor controller. (e.g. using a L298N, you use one pin for your PWM signal (speed), and two pins for direction (both high = hard brake, one high = forward, other high = back, both low = coast)).

Unlike a regular motor, in a stepper motor, you turn on individual coils inside it, causing the rotor to move slightly each time. When you energize one of the coils, the magnetic field will attract the nearest rotor teeth causing them to align with it and then hold in place. You then energize the next coil causing the rotor to move another few degrees. It is common for stepper motors to give you 100 steps (3.6 degree) to 200 steps (1.8 degrees) per rotation. This means that if you know the number of steps (and wheel size), you can have a good idea of distance traveled. Since you are controlling each coil, you typically need either 2 or 4 outputs from your microcontroller to control the stepper motor (and again, since you are directly powering a motor, need a chip that can source the necessary current (e.g. a ULN2003A).

In terms of determining position, there are several ways:


For a rough approximation, you can simply use the run time - keeping in mind however, that there is acceleration/friction that will mean the distance/time curve is non-linear.
A reasonably accurate measure is the number of steps moved by a stepper motor (although this is still an estimate - in some cases a step signaled might not result in a step taken).
The best kind of measures will actually look at wheel movement, and use them as a feedback mechanism. One such method is to use a rotary encoder. Essentially, you have a disk with dark areas and light areas (or holes and solid parts, etc.) and you use a reflectance sensor to count the number of times a dark/light area passes in front of it (which will give you how many times the wheel actually spins). (You could probably connect your wheels to a mouse encoder as well). 
If you want relative position, then other sensors (ultrasonic/IR - distance, contact (e.g. microswitches), etc.) may be more useful.