Phase margin is the difference in degrees from -180 deg, when the gain of the amplifier is 1, or 0dB. Similarly, the gain margin is the difference in dB from 0dB, when the phase is -180deg.
It all has to do with the characteristic avoiding the critical point (-1,0). Both of these parameters tell you how well you avoid the critical point. So both are a measure of stability. The greater the phase margin, the farther from the critical point the characteristic passes, so the more stable the system. Similarly, the greater the gain margin, the more stable the system, because again, the characteristic passes farther from the critical point .
Take a look at the picture. It's not accurately drawn, but it should help get the idea. A perfect picture can only be drawn using some math program, but I was in a hurry.
The top figure shows the Bode diagrams. The phase margin is the difference from actual phase and -180 deg when the gain (red) crosses 0dB. The gain margin is the amount of (negative) gain when the phase crosses -180 deg.
The bottom picture is the Nyquist plot (I wish I could say for the same system, but I do not draw so accurately). Anyway, as you can see, a gain of 1 is at the intersection of the characteristic with the unity circle. Then the phase margin is the angle difference to -180 deg, when the gain is 1 (equiv. to 0dB above).
When the phase is -180 deg, you get the gain margin as the "difference" from actual characteristic and a gain of 1. (Many will not agree with this, strictly speaking, but I find it very easy to picture in my mind).
I hope this helps.