Smith Chart Explanation
To give a very quick explanation of the Smith chart, it rests on one simple idea:

The reflection coefficient (\$\Gamma\$ or \$S_{11}\$) of a termination on a transmission line is related to the impedance of the termination (Z) by

\$\Gamma=\frac{Z-Z_0}{Z+Z_0}\$

Where \$Z_0\$ is the characteristic impedance of the line. All of these variables are complex numbers.

The Smith chart is a graphical means of calculating this relationship.

Basically you plot the reflection coefficient on the chart in polar coordinates: the distance of the point from the center of the chart is the magnitude of the reflection coefficient, and the angle from the x-axis is the argument of the reflection coefficient. Then the lines on the chart enable you to read off the load impedance. Often the chart is normalized to a characteristic impedance of 1 Ohm, so you'd multiply the read load impedance by your actual Z0 (often 50 Ohms) to get the physical load impedance.

Conversely you could plot your load impedance value by reference to the lines drawn on the chart, and read off the reflection coefficient by using a ruler to measure the distance from the chart's center and to locate the angle from the scale around the outer edge.



It's useful to be able to quickly switch between reflection coefficient and load impedance because certain circuit adjustments have an effect that's more easily calculated in one form or the other. 

For example, adding a series resistor adds a fixed value to the real part of the load impedance. Or adding a series inductor adds a frequency-dependent value to the imaginary component of the load impedance. On the other hand, moving back along the transmission line to a point further away from the load adds a frequency-dependent value to the phase of the reflection coefficient. 

The curves drawn on the chart posted by Russell show examples of these kinds of transformations.

I should add that there's an alternative form of the Smith chart, called an admittance Smith chart, that looks the same but mirrored across the y-axis. This allows calculating the relationship between admittance and reflection instead of impedance. It's useful, for example, if you are adjusting your load by placing a parallel element instead of a series element.