Also known as Continuum Distortion Propulsion.
Warp drive works by accelerating from slower than light speed to faster than light speed in less than Planck time, therefore, never actually being at exactly light speed. There are two warp scales: the old one and the new one.
Old Warp Scale
See tribbel's writeup above.
New Warp Scale
For warp 1-9, the formula is speed(warp_factor) = warp_factor10/3c. After that, it approaches infinity without limit. Wikipedia claims that portion is based off a hand-drawn curve, so no actual formula.
TOS and TAS use the old one, TNG, DS9 and VOY used the new.
In Star Trek: Voyager, they reached warp 10 which basically meant they were going infinite speed: they were everywhere in the universe at once. There's great debate about the use of warp 13 in All Good Things...
Special types of warp drive include Coaxial Warp, Quantum Slipstream, and Transwarp. Soliton waves also work for ftl travel, but are a very different concept. For slower than the speed of light travel they use Impulse Drive.