More than you've ever wanted to know about the C wire:
Lets start by explaining what the C wire is, and why it's needed.
Ye olde thermostat
In the olden days thermostats were simple switch devices, that used Mercury Switches to complete the circuit and turn on the heat/AC.
Mercury switches were commonly used in bimetal thermostats. The weight
of the movable mercury drop provided some hysteresis by moving the
bimetal spring slightly beyond the point it would normally assume,
thereby holding the thermostat off slightly longer before flipping to
the on state and then holding the thermostat on slightly longer before
flipping back to the off state. The mercury also provided a very
positive on/off switching action and could withstand millions of
cycles without degradation of the contacts.
Source
Because of this, there was no reason to run a return wire ("neutral" or C) wire to the thermostat. For example a thermostat that only controlled heat, would only required 2 wires.

Welcome to the future
Newer thermostats that offer clocks, backlit displays, WiFi, etc. are controlled using circuit boards and integrated circuits. These new circuits require a path for electricity to return to the source, and so require an extra wire. This new wire is known as the C wire, or Common wire.

How do I get a C wire?
If you're lucky when you upgrade to a newer thermostat that requires this connection, there will be an extra (unsused) wire in the cable at the thermostat. If you're not, you'll have to run new cable to the thermostat.
If you have heat and AC, you'll have to pull an 18/5 cable. If you have just heat you can get away with pulling 18/3 cable, but you may want to pull 18/5 anyway to make adding AC in the future easier.

What do all these wires do anyway?
There are no standards for wire color, so any wire could be used for any purpose. The most common color code would be (note: this is for forced air furnaces, heat pumps and other systems may be different).
- Red -
R - 24VAC
- Red -
Rh - 24VAC (dedicated to heat call)
- Red -
Rc - 24VAC (dedicated to cooling call)
- Green -
G - Fan on
- White -
W - Heat call
- Yellow -
Y - Cool call
- Blue or Black -
C - Common (neutral)
Alternative Solution
This solution is illustrated in this video from Honeywell. With this solution you lose the ability to manually turn on the blower fan, but the fan will still run properly in the Auto position.
WARNING: This procedure involves modifying the wiring in the furnace, and may not be approved by every manufacturer. Check with the furnace manufacturer, and all local codes before attempting this procedure. Make sure the breaker for the furnace is OFF before you begin.
- Make sure the breaker for the furnace is OFF.
- Start by removing the access panel on the furnace, and locating the thermostat wires.
- Remove the wire from the
G terminal, and connect it to the C terminal.
- Using a short piece of 18 AWG wire, make a jumper and connect it between the
Y and G terminals (this is only required if you have both heat and central air).
- Replace the access panel.
- Remove the thermostat from the wall to gain access to the wiring.
- Remove the wire from the
G terminal, and connect it to the C terminal.
- Replace the thermostat.
- Turn the furnace breaker back on.
A bit more about transformers and C wires.
A transformer uses coils of wire, magnetism, and a bit of magic to transfer energy from the primary side of the transformer to the secondary side of the transformer. Usually during the transfer, the voltage is either increased or decreased. In the case of our furnace we're likely talking about taking 120VAC, and transforming it into 24VAC. Once the voltage has been reduced, we can use the lower voltage and a thermostat to control the furnace.
Now that you know even less about transformers than you did before, lets look at a diagram.

This is an actual wiring diagram from a furnace, but you'll notice I've highlighted a few things. First, in red I've highlighted the 120V primary side of the transformer. I've also highlighted the secondary side of the transformer in a couple shades of blue. This was done to illustrate that one side of the transformers secondary winding (light blue), is attached to the R or power terminal. While the other side of the secondary winding (dark blue), is attached to the C or "neutral" terminal.