The preceding write ups missed a few important points about MAD.
First, for MAD to work, both sides have to have amassed arsenals that are either impervious to retaliatory strikes (such as SLBM's or deeply buried and dispersed ICBMs) or such an overwhelming number of nuclear weapons, a first strike cannot possibly destroy them all.
Secondly, and this follows from the first, each side must have a credible second strike capability. In other words one side must have a reserve of weapons capable of surviving a first strike, and the other side must recognize and understand this fact. This closes the loop, so to speak, on the "mutually assured" part of MAD.
Finally, for MAD to be effective, one must have a credible and well known doctrine for the use of nuclear weapons. The Soviets and the United States, throughout the Cold War, made perfectly clear under what circumstances they would resort to nuclear weapons. Through public documents, highly visible military exercises, nuclear tests, and diplomacy both sides were able to make the threat of their nuclear capabilities credible.