At least since the days of Darwin, evolution has been associated with the increase of complexity: if we go back in time we see originally only simple systems (elementary particles, atoms, molecules, unicellular organisms) while more and more complex systems appear in later stages. However, from the point of view of classical evolutionary theory there is no a priori reason why more complicated systems would be preferred by natural selection. Evolution tends to increase fitness, but fitness can be achieved as well by very complex as by very simple systems. For example, according to some theories, viruses, the simplest of living systems, are degenerated forms of what were initially much more complex organisms. Since viruses live as parasites, using the host organisms as an environment that provides all the resources they need to reproduce themselves, maintaining a metabolism and reproductory systems of their own is just a waste of resources. Eventually, natural selection will eliminate all superfluous structures, and thus partially decrease complexity.
Complexity increase for individual (control) systems
The question of why complexity of individual systems appears to increase so strongly during evolution can be easily answered by combining the traditional cybernetic idea of the "Law of Requisite Variety" and a concept of coevolution, as used in the evolutionary "Red Queen Principle".
Ashby's Law of Requisite Variety states that in order to achieve complete control, the variety of actions a control system should be able to execute must be at least as great as the variety of environmental perturbations that need to be compensated. Evolutionary systems (organisms, societies, self-organizing processes, ...) obviously would be fitter if they would have greater control over their environments, because that would make it easier for them to survive and reproduce. Thus, evolution through natural selection would tend to increase control, and therefore internal variety. Since we may assume that the environment as a whole has always more variety than the system itself, the evolving system would never be able to achieve complete control, but it would at least be able to gather sufficient variety to more or less control its most direct neighbourhood. We might imagine a continuing process where the variety of an evolving system A slowly increases towards but never actually matches the infinite variety of the environment.
However, according to the complementary principles of selective variety and of requisite constraint, Ashby's law should be restricted in its scope: at a certain point further increases in variety diminish rather than increase the control that system A has over its environment. A will asymptotically reach a trade-off point, depending on the variety of perturbations in its environment, where requisite variety is in balance with requisite constraint. For viruses, the balance point will be characterised by a very low variety, for human beings by a very high one.
This analysis assumes that the environment is stable and a priori given. However, the environment of A itself consists of evolutionary systems (say B, C, D...), which are in general undergoing the same asymptotic increase of variety towards their trade-off points. Since B is in the environment of A, and A in the environment of B, the increase in variety in the one will create a higher need (trade-off point) in variety for the other, since it will now need to control a more complex environment. Thus, instead of an increase in complexity characterised by an asymptotic slowing down, we get a positive feedback process, where the increase in variety in one system creates a stronger need for variety increase in the other. The net result is that many evolutionary systems that are in direct interaction with each other will tend to grow more complex, and this with an ever increasing speed.
As an example, in our present society, individuals and organizations tend to gather more knowledge and more resources, increasing the range of actions they can take, since this will allow them to cope better with the possible problems appearing in their environment. However, if the people you cooperate or compete with (e.g. colleagues) become more knowledgeable and resourceful, you too will have to become more knowledgeable and resourceful in order to respond to the challenges they pose to you. The result is an ever faster race towards more knowledge and better tools, creating the "information explosion" we all know so well.
The present argument does not imply that all evolutionary systems will increase in complexity: those (like viruses, snails or mosses) that have reached a good trade-off point and are not confronted by an environment putting more complex demands on them will maintain their present level of complexity. But it suffices that some systems in the larger ecosystem are involved in the complexity race to see an overall increase of available complexity.
Complexity increase for global (eco)systems
The resoning above explains why individual systems will on average tend to increase in complexity. However, the argument can be extended to show how complexity of the environment as a whole increases. Let us consider a global system, consisting of a multitude of co-evolving subsystems. The typical example would be an ecosystem, where the subsystems are organisms belonging to different species.
Now, it is well-documented by ecologists and evolutionary biologists that ecosystems tend to become more complex: the number of different species increases, and the number of dependencies and other linkages between species increases. This has been observed as well over the geological history of the earth, as in specific cases such as island ecologies which initially contained very few species, but where more and more species arose by immigration or by differentiation of a single species specializing on different niches (like the famous Darwin's finches on the Galapagos islands).
As is well explained by E.O. Wilson in his "The Diversity of Life", not only do ecosystems contain typically lots of niches that will eventually be filled by new species, there is a self-reinforcing tendency to create new niches. Indeed, a hypothetical new species (let's call them "bovers") occupying a hitherto empty niche, by its mere presence creates a set of new niches. Different other species can now specialize in somehow using the resources produced by that new species, e.g. as parasites that suck the bover's blood or live in its intestines, as predators that catch and eat bovers, as plants that grow on the bovers excrements, as furrowers that use abandoned bover holes, etc. etc. Each of those new species again creates new niches, that can give rise to even further species, and so on, ad infinitum. These species all depend on each other: take the bovers away and dozens of other species may go extinct.
This principle is not limited to ecosystems or biological species: if in a global system (e.g. the inside of a star, the primordial soup containing different interacting chemicals, ...) a stable system of a new type appears through evolution (e.g. a new element in a star, or new chemical compound), this will in general create a new environment or selector. This means that different variations will either be adapted to the new system (and thus be selected) or not (and thus be eliminated). Elimination of unfit systems may decrease complexity, selection of fit systems is an opportunity for increasing complexity, since it makes it possible for systems to appear which were not able to survive before. For example, the appearance of a new species creates an opportunity for the appearance of species-specific parasites or predators, but it may also cause the extinction of less fit competitors or prey.
However, in general the power for elimination of other systems will be limited in space, since the new system cannot immediately occupy all possible places where other systems exist. E.g. the appearance of a particular molecule in a pool of "primordial soup" will not affect the survival of molecules in other pools. So, though some systems in the neighbourhood of the new system may be eliminated, in general not all systems of that kind will disappear. The power for facilitating the appearance of new systems will similarly be limited to a neighbourhood, but that does not change the fact that it increases the overall variety of systems existing in the global system. The net effect is the creation of a number of new local environments or neighbourhoods containing different types of systems, while other parts of the environment stay unchanged. The environment as a whole becomes more differentiated and, hence, increases its complexity.
See also:
Heylighen F. (1996): "The Growth of Structural and Functional Complexity during Evolution", in: F. Heylighen & D. Aerts (eds.) (1996): "The Evolution of Complexity" (Kluwer, Dordrecht). (in press)
T.S. Ray: 
An evolutionary approach to synthetic biology
Dam McShea and the great chain of Being: does evolution lead to complexity?
W. Brian Arthur: "Why Do Things Become More Complex?", Scientific American, May 1993
PRNCYB-L discussion on Requisite Variety, Complexity & the edge of Chaos
