Fairy rings are natural fungus growths firmly entrenched in superstition because the process by which the ring forms is not popularly understood; rings don't generally occur as natural formations. The key to understanding is knowing that the important parts of the organism we call a mushroom is underground. The recognizable stem and cap is really only the reproductive portion of the fungus, called the sporophore. The true body of the organism is hidden from view and much larger.
A fairy ring begins as a single point of underground fungus growth, likely planted by tiny floating spores from another mushroom far away. Over a number of years, the fungus begins to grow and branch out as tubular filaments called hyphae. As the hyphae grows, it tangles and interweaves into a mat called mycelium. The mycelium is the real body of the mushroom fungus, and is hidden growing inside its source of nutrients (tree bark, roots, decomposing material, soil, etc). The mycelium secrets enzymes which digest and absorb nutrients from its growth medium.
In some cases, the mycelium growth can be relatively uniform and expands in a rough circular shape. The longer it has to grow, the larger the circle can be (specimens have been found up to 50 feet (15 meters) in diameter). If the circle is incomplete or unable to grow in a certain direction, the fairy ring may become an arc or crescent instead. This tangled mat of mycelium can grow, hidden from view, for years and even centuries in some species.
When conditions are right (day length, heat, humidity, moisture, soil quality, etc.), the mycelium buds into much more organized growths of hyphae which form the large visible structures of stem and cap called sporophores, or what most people know as mushrooms. This process can happen very quickly, often overnight. A single mat of mycelium can produce several sporophores at scattered points along its growth. After several weeks, the mushroom is capable of producing spores and fulfills its purely reproductive purpose.
It is the combination of even, circular mycelium growth hidden underground and rapid development of sporophores which creates the structures called fairy rings. The rings can alternatively be the result of a pile of buried, decaying matter or tree stumps and roots on which the fungus is feeding. This is a common occurrence in newly cleared land, especially golf courses. Several species of mushrooms are capable of forming fairy rings, some of which are poisonous.
While the actual sporophore growths only occur once in a while, fairy rings can also manifest themselves as a ring of dead grass (called necrotic fairy rings) or a ring of very dark green grass, and sometimes as a ring of dark green grass around a ring of dead grass. Death occurs due to the water-resistant layer of mycelium which prevents water from reaching the grass roots. The dark green grass coloration is due to the fungus releasing large amounts of nitrogen into the soil as it feeds.
Fairy rings are a nuisance for lawns because it is difficult to kill the entire organism. Merely removing the mushroom portions is not enough, since they are just the reproductive organs. Fungicide can prove to be only a temporary cure, since the underground mat of mycelium can form a water-resistant layer the fungicide cannot penetrate. Good results have been achieved by aerating the soil in the area before using fungicide. In the case of fungus growing on decomposing buried material or stumps, these will have to be dug up and removed.
Thanks to elwen for pointing out to me why mushrooms sprout so quickly. The initial bud from the mycelium is formed by the slow process of cell division, but the sporophore then expands by cell inflation. It gets bigger by pumping more water into the cells.