First, a few necessary definitions:

A system is (from the control engineer's point of view) made up of a plant, (perhaps an airplane) and some control laws.  A closed-loop system includes some control augmentation helping to control the system. An open-loop system has the control laws disconnected from the plant.

]In the case of many older transport aircraft, a stability augmentation system feeds back yaw rate gyro measurements into the rudder to improve the damping of the dutch roll mode - a nuisance corkscrewing motion that is a characteristic trait of conventional, cruciform aircraft. Military and newer aircraft include more sophisticated control augmentation systems.]

An signal is some time-varying property of the plant that can be measured.

An output signal or output is a signal that is not directly controlled.

An input signal or input is a signal that is directly controlled (whether by a human or an artificial controller).

The gain of a system is the amplification or attenuation of the principal output compared to the principal input.

[Imagine the input is the pilot's stick position, and the output is the pitch rate of the airplane.  In a typical stability-augmentation case, the pitch rate of the aircraft is measured by gyros and is fed back to the elevator (and added to the pilot's input signal). So the gain of the open-loop system is how much the airplane amplifies or attenuates the pilot's stick position signal in its pitch response. In the closed-loop system, the open-loop gain is MULTIPLIED by the feedback gain on the pitch rate gyro signal.  Increasing the overall gain could be achieved by changing the strength of the pitch rate gyro signal (relatively easy) OR by changing the dynamics of the airplane (not so easy, but possible).]

Most systems that contain oscillatory (2nd order or higher) dynamics will, if the overall gain of the system is increased, go unstable.  [In our airplane example, an aircraft is usually a fourth-order system, with two characteristic longitudinal modes of motion: the short-period and the phugoid.] Thus, controls weenies talk about how much the gain can be increased before instability occurs.

Now imagine that the pilot is capable of generating perfect sine waves at any frequency.  The airplane will respond by bobbing its nose up and down; the resulting strip chart trace of pitch rate will be a sine wave.

If you ask the pilot to put in a sine wave at various frequencies, and look at the resulting aircraft response, you can plot the amplitude ratio between input and output, and the phase difference (in degrees), for each frequency. The resulting plots constitute the Bode amplitude and phase plots that are then used to calculate gain and phase margin.

A typical system will show an amplitude ratio near unity and zero phase lag (i.e. perfect correlation) for low-frequency inputs, with an amplitude drop off at some point and decreasing amplitude response at higher frequencies. This drop off point is often called the crossover or bandwidth of the system (you can demonstrate these easily in most GA aircraft - at some very high stick pumping frequencies, the only response you get is structural - no pitch response at all). Correlated with the drop off is a relatively rapid change in phase margin - near the crossover/bandwidth frequency, the plant's output stops tracking the input signal closely, and falls farther behind in phase.

An instability occurs when the feedback signal used to stabilize the plant is 180 degrees out of phase with the output of the plant, IF the gain of the system at that point is larger than unity.

Thus, the gain margin is a measurement of how high the gain of the plant can be increased before the gain of the system AT THE 180 DEGREE PHASE LAG frequency reaches unity.

The phase margin is a measurement of how many degrees remain before reaching 180 degrees phase lag at the point AT WHICH SYSTEM GAIN crosses unity.

Designing a control system with gain and phase margins allow for variations in the plant and sensors (which are never exactly known).

For most control systems, a rule-of-thumb is to provide gain to double (also known as 6 dB) without incurring instability, or to provide 45 degrees of phase lag at the crossover frequency.