Thermostat Connections with Arduino
It looks like the "accepted" way to connect the thermostat wires is to use a bi-stable, or "latching" relay. The thermostat in my house uses the Omron G65SK-2-H-3 relay. It looks like its a 3V, low signal, latching relay that can handle the 24v connection from the thermostat wires (which, if I understand correctly, controls a bigger relay that actually supplies power to the unit). 

The reason for using this special kind of relay seems to be that thermostats are usually battery powered. So if you use a regular relay, it will drain that battery as it holds the relay open. If you use a latching relay, you just send a quick pulse to the relay and then it holds in that position until it receives another pulse.

If you look for these relays on ebay and digikey, they seem to go for about $3-$5 each. After some searching, I found a pack for 10 for about $2 each. The searches I used were:
 * "5v latching relay"
 * "low signal latching relay"
 " "G6SK-2-H" (although I did not end up getting this exact relay)

If you design the thermostat so that it plugs into the wall, you probably don't have to worry about using this special kind of relay.