How do we replace an old 3-wire thermostat with a 4-wire one?
Run a new cable
If you want to add cooling, you're likely going to have to run a new cable. Depending on when and how the current cable is installed, you may be able to use the current cable to pull the new cable. If not, you may be able to fish the new cable along side the current cable.
Use an existing wire
The other option, is to repurpose one of the wires in the cable. The down sides to this approach are that it may not be supported by some control boards, and you won't be able to control the blower fan independently.
Before you decided to add A/C, your furnace thermostat relationship looked something like this.

You had a 3 wire cable that ran between the two, and that's all you needed. Now that you've decided to add A/C, the picture has changed a bit.

So now you need to find a way to connect the Y terminals, so your thermostat can tell the A/C when to turn on and off.  You could run a new cable with an extra wire; which is the more correct way to do it, or you can use an existing wire.  Start by disconnecting the wire from the G terminal in the thermostat, and connecting it to the Y terminal instead.  Next, do the same in the furnace.  Now you have a wire that the thermostat can use to tell the A/C unit when to turn on/off, but you're not quite done.  When the A/C comes on, the furnace blower needs to be on too, so the cool air can circulate throughout the house.  To accomplish this, you'll simply install a jumper between the Y and G terminals in the furnace.  Now whenever the thermostat sends the signal for cool, the furnace also receives the single to turn the fan on.

As stated above, if you do this the FAN setting on the thermostat will do diddly squat. You should also check with the furnace manufacturer before doing this, to make sure they support this configuration. Also, don't forget to shut off the breaker for the furnace before working on the furnace or thermostat.
More information on this solution; including a video, can be found in this answer.