Combo deck is a term for a deck of (usually sixty) Magic: The Gathering cards that aims to win the game using a relatively small number of cards that instantly or very quickly win the game when combined (hence the name "combo").  Because of this win strategy, a common motif among combo decks is an emphasis put on the ability to find specific cards quickly and win as fast as possible.   
Combo history and development
Early combo decks generally had a one-shot strategy that resulted in a win under most game conditions. As newer sets were released, however, it was realized that most combo decks generally need two things that were missing: 1) alternate win conditions, or awcs, and 2) ways to deal with your opponent's threats.
Alternate win conditions usually consist of a few powerful cards that often have nothing to do with your combo but can win you the game if somehow your combo does not work. Most often these AWCs are a few very powerful creatures like Darksteel Colossus in Eternal formats or Meloku the Clouded Mirror when it was legal in Standard Constructed.
Common ways to deal with your opponent's threats include Counterspells, discard spells, and creature destruction. These spells are often used in combo decks most strategically when they are used not as much as offensively as they are used defensively. In other Control decks, these cards are used to fight the opponent and their spells, but in Combo decks, these cards are used to keep you alive, or "stall", until you can play your combo and win.
As a result, these two aspects have greatly improved Combo's reliability. Today, these two aspects can be found in almost every competetive Combo archetype.
Examples of Combo Decks
Channelball is the classic example of early combo strategies because it deals exactly twenty damage, the amount required to win a game, and is playable on the first turn if the right cards are drawn in an opening hand. The basic strategy was to drop quick mana, including Black Lotus or Mox artifacts, cast a Channel and a Fireball, using excess mana to pump the Fireball up one or two damage, and using Channel to fuel the Fireball for the rest of the damage necessary to kill one's opponent. The ensuing 20-point Fireball would kill one's opponent, and leave the caster usually between 1-5 life. Because Channelball was quite vulnerable to essentially fatal disruption (e.g., a Counterspell, or retaliatory Lightning Bolt) it was superseded by more robust, fast, and powerful combo decks.
Prosperous Bloom (Bloom-Drain)
The first modern combo deck, it utilized Squandered Resources to cast an early Cadaverous Bloom. Prosperity is cast, and one's hand discarded to gain a large number of cards. Successive Prosperities then increase your hand size dramatically. A card is thrown to cast a Drain Life, and ten cards are thrown to fuel the Drain for 20 points. 
A type of blue control/deck destruction, TurboZvi used Dream Halls and massive card drawing to create a combo. The player would pitch a blue card to cast a blue card drawing spell for a net gain of cards. Mana Severance would be used to remove land cards from the deck to improve the efficiency of card drawing, while Gaea's Blessing would be used to cycle one's graveyard back into their deck. The win was through destruction of the opponent's deck with cards like Inspiration or Lobotomy.
Fruity Pebbles used Goblin Bombardment to deal massive amounts of damage using a loop, in which a single play was repeated many times to the player's advantage. An artifact creature playable for no mana, for example, Phyrexian Walker or Ornithopter, designed as a cheap and expendable blocker, was combined with Enduring Renewal, a card that automatically returns dying creatures to their owner's hand. The player then sacrificed Ornithopter or some equivalent to Goblin Bombardment to deal damage to their opponent; the Ornithopter returned to their hand, was played for no mana, and the cycle repeated until the opponent was defeated. This combo was stronger than previous ones because its game pieces could be used to some effect even outside its combo. This principle, which suggests that combo pieces should be useful in as many contexts as possible, is a fundamental guiding principle in the construction of contemporary combo decks.
Reaplace (Reap-Lace Combo)
Reaplace marked another deck-design breakthrough that is still very relevant to today's combo decks: complexity and versatility. Whereas many other previous combo decks relied on one card combo without which it was dead, reap-lace players were highly innovative and built multiple win conditions into their decks. The combo itself is considered somewhat silly by today's standards because it involves cards that are highly situational outside of the combo and have little synergy unless all of the combo cards are present. However, the idea that a combo player can win more games by his play skill than by his luck started largely with this deck and is one of the greatest considerations in deck design today.
Later combo decks
Because the actual deck combos are hard to understand without a detailed knowledge of Magic: The Gathering rules and actual decklists vary greatly, there is no easy and encyclopedic way to present information regarding specific combo decks. However, for reference, here is a list of combo decks that have been prominent in Magic: The Gathering history.
- Academy, Neo-Academy (Tolarian Academy + Stroke of Genius)
- Aluren (Aluren + Pandemonium + Cavern Harpy or Horned Kavu)
- Angry Hermit (Hermit Druid + Reanimate + Sutured Ghoul)
- Belcher Combo (Goblin Charbelcher + Mana Severance)
- Bomberman (Lion's Eye Diamond + Auriok Salvagers + Pyrite Spellbomb)
- Brain Freeze (Heartbeat of Spring + Mind's Desire + Early Harvest + Brain Freeze)
- Cephalid Breakfast (Cephalid Illusionist + Nomads en-Kor + Reanimate + Sutured Ghoul)
- Dark Depths (Dark Depths + Vampire Hexmage)
- Desire (Mind's Desire + Cloud of Faeries + Snap)
- Doomsday Combo (Doomsday + Mind's Desire + Beacon of Destruction)
- Dragon Combo (Animate Dead + Worldgorger Dragon)
- FEB (Full English Breakfast) (Volrath's Shapeshifter + Phyrexian Dreadnought)
- Firemind (Niv-Mizzet, the Firemind + Curiosity or Ophidian Eye)
- FlameVault (Flame Fusillade + Time Vault) (no longer possible with current wording of Time Vault)
- Goblin Food Chain/Skullclamp Goblins
- Heartbeat Combo/Weird Harvest (Heartbeat of Spring + Early Harvest + Blaze)
- Hulk Flash (Protean Hulk + Flash)
- Iggy Pop (Intuition + Ill-Gotten Gains + Tendrils of Agony)
- KCI combo (Krark-Clan Ironworks + Myr Incubator)
- Life.dec (Nomads en-Kor + Task Force + Worthy Cause)
- Long.dec, LongDeath/Death Long, Grim Long (Tutor/Wish + Tendrils of Agony)
- Natural Order (Natural Order + Progenitus)
- Oath Combo (Oath of Druids + Auriok Salvagers)
- Savage Game (Gamekeeper + Auriok Salvagers)
- Solidarity (High Tide + Reset)
- Splinter Twin (Deceiver Exarch + Splinter Twin, Pestermite and Kiki-Jiki, Mirror-Breaker can also be used)
- Painter (Painter's Servant + Grindstone)
- Replenish Combo (Replenish + Opalescence)
- Thopter Combo (Thopter Foundry + Sword of the Meek)
- TPS (The Perfect Storm)
- Tinker Combo (Tinker + Darksteel Colossus or Blightsteel Colossus)
- Trix/Rector Trix/Rectal Agony (Donate + Illusions of Grandeur)
- Vault/Key (Time Vault + Voltaic Key)
Yet more combo decks have been developed and built by many people, but are not fast enough or deadly enough to become popular tournament decks.
- ElfBall (Priest of Titania + Banefire)
- MindSlaver (Bringer of the White Dawn + Mindslaver)
- Myr Swarm (Myr Matrix + Mana Echoes)
- Saproling Burst Combo (Pandemonium + Saproling Burst)
- Scrap (Blasting Station + Grinding Station + Salvaging Station + Summoning Station)
- Sliver Swarm (Sliver Queen + Mana Echoes)
- Squirrel Swarm (Squirrel Nest/Earthcraft)
- Stasis (Stasis/Chronatog)
- The Unspeakable (Peer through Depths + Reach through Mists + Sift through Sands)
- Warp World (Warp World + Anarchist)
Some decks are not categorized strictly as combo decks, but still have elements of a combo deck.
- Affinity Combo (Arcbound Ravager + Disciple of the Vault)
- Enduring Ideal (Enduring Ideal + Form of the Dragon + Zur's Weirding)
- Greater Good
- MaskNaught (Illusionary Mask + Phyrexian Dreadnought)
- Miracle Gro/Gro-A-Tog (Quirion Dryad + Psychatog)
- OmegaBurnDeck (Urza's Rage + Fork)
- Psychatog (3 or 4-color)
- Tooth and Nail
- Wake (Mirari's Wake, particularly Mirari and Cunning Wish)
- Mark Rosewater. (September 27, 2004.) "Combo Platter", Daily MTG, magicthegathering.com, Wizards of the Coast.
- Shuhei Nakamura. (March 31, 2007.) "Your First Combo Deck", Daily MTG, magicthegathering.com, Wizards of the Coast.
- Jeff Cunningham. (June 16, 2007.) "Playing Against Combo", Daily MTG, magicthegathering.com, Wizards of the Coast.
- Aaron Forsythe. (October 01, 2004.) "Combos? What Combos?", Daily MTG, magicthegathering.com, Wizards of the Coast.
- The Mana Drain: Online forum features some of Magic: The Gathering's greatest combo innovators.
- Star City Games: Features many decklists and explanations of combo decks of the past, present, and future.
- The Source: Your source for Legacy. Includes all the Tier 1 Legacy decks, and discussion on them.