Evolution can seem pretty astonishing by itself. The varied and specific adaptations used by many organisms can seem at times to defy logic. Symbiosis only makes it seem more unlikely -- how could two separate species evolve traits that just happen to fit so perfectly together? In fact, many people who question evolution point to symbiosis as "proof" that these couldn't happen naturally.
Natural selection is the key to understanding how symbiosis evolves. In a given population, some organisms will have traits that are more advantageous to successful reproduction than others. Organisms with those traits are therefore more likely to pass them along to succeeding generations, while those without them have a greater chance of dying before they reproduce. Thus, over many generations, the population will tend to look more and more like the individuals with the successful traits.
The success or failure of traits depends on population pressure -- circumstances that make it more difficult for individuals to survive. Traits that allow a creature to take advantage of the other life forms in its environment will be just as successful as the traits that allow it to escape (or eat) them.
Most symbiotic relationships probably started out as facultative. Over many generations, the organisms came to depend more on the symbiosis because natural selection favored those traits and not others. Eventually, the symbiosis became the sole source of the food, shelter, enzyme or whatever else the symbiotes derived from one another.
Another way to look at symbiosis is as evolution's toolbox. Trees need the nutrients found deep within the soil. They could evolve more efficient root systems that would allow them to extract those nutrients themselves -- in fact, many trees have. But this can take a lot of time (tens of thousands of years or more) and might not happen at all. It just so happens that fungi already have this ability. When the two species find themselves in close proximity, it is much faster to evolve a way to incorporate the "tool" already available to the other organism than to reinvent the wheel.
Some biologists are proponents of a theory known as symbiogenesis. This theory, which has fairly widespread acceptance, suggests that symbiosis is actually the key to the origins of complex life on Earth. Symbiogenesis theorists think that increasingly diversified microbes entered into a series of symbiotic relationships, with different microbes performing the tasks vital to microbial existence. These relationships evolved into a tightly integrated network of reciprocal microbes, each acting as a cog in the machine. They eventually evolved a casing enclosing them all. The microbes that made up this "team" became the parts of a cell: mitochondria, nuclei, ribosomes.