The Common wire is the hot black wire.
Here's a well written, thoughtful article explaining the common wire in a three-way switch, that should lay to rest the tentacled monsters these things can appear to be to DIYs:
http://www.naturalhandyman.com/iip/infelectrical/inf3way.html
According to The Natural Handyman, the common wire is the "hot" wire leading to the lamp fixture, or fed from the breaker box, and in modern buildings, is usually black. The other wires are called "travellers," usually white, and once the common wire is identified, and the green "ground" wire attached, the others can be hooked up to whichever connections are left. He strongly advises replacement of the both switches, as both will have suffered from the failure of either, and it's better to be safe, than sorry.
I found the advice on using a multimeter (inexpensive and commonly available) very useful in identifying the common wire. Trip the circuit breaker, remove the switch, widely separate the wires, switch on the circuit, set the multimeter to 110v, then touch one of the probes on the box's ground wire, and the other to each of the remaining wires. Only one of them should register a current, which makes it the "common" wire.
Turn off your breaker again, and install your master switch. Repeat for the slave switch, this time setting your multimeter to "infinite resistance" or "continuity". It will beep when you've found the correct wire.
If you find more than one hot wire, it's probably because one of the switches in the gang box controls an outlet (for table lamps, etc.), while the other outlet is always hot. Refer to the link for a very detailed explanation, and the fix.
Hope this was helpful!
-Johnzane