A rainbow table is a lookup table designed to help recover plaintext from a one-way hash. It is created by collecting all possible (in theory) plaintexts of a specific nature (length, character set) and their respective outputs from a hash function. In short, it's a code book for a hash function. These tables can then be used to run quick brute-force attacks against hashes. Due to their nature, rainbow tables are very large (ranging from 500 megs to 40 gigs), and take many days to compute, depending on processor speed. This is known as a time-memory tradeoff because it consumes enormous time to create, but once they are created password recovery is -very- quick.

For more information, check out:
"A Cryptanalytic Time-Memory Trade-Off" (Marty Hellman)
"Making a Faster Cryptanalytical Time-Memory Trade-Off" (Philippe Oechslin)

There are also a few active rainbow table projects:
http://www.antsight.com/zsl/rainbowcrack/ (tools to create your own rainbow tables)
http://rainbowcrack.com/ (contribute to a world-wide effort to create rainbow tables)
http://rainbowtables.shmoo.com/ (rainbow tables of different sizes, compliments of Shmoo group)