After a little research, I feel confident that I can make a stab at some kind of basic explanation of Complexity Theory, and how it is relevant to our understanding of the world. However, my knowledge is still extremely limited, and I don't presume to know all of the...complexities...of the theory. So, take this for what it is, just a brief, limited overview of the subject.
The first thing to say about Complexity Theory is that there isn't one - a theory, that is. There is no unifying, underlying concept of complexity, what makes something complex, how one thing is more or less complex than another, how complexity emerges, etc. Furthermore, there is no such thing as a "complexity science" since it incorporates a whole array of very different lines of thought and covers a broad spectrum of disciplines. Complexity studies might be a better term, but I'm not sure even that quite fits. (See the following website for an idea of the various threads of Complexity)
I'm not sure it matters that there is no "Complexity Theory" or that there is no working definition of "complexity," though. I'm beginning to see, as Bateson did with cybernetics and General Systems Theory, that Complexity is not so much a "theory" as an epistemology - a way of understanding. It doesn't seek to describe any particular phenomena, but provides a framework for looking at a variety of phenomena.
Prior to the 20th century, the dominant epistemology was the clockwork universe which functioned in terms of serial causation. Complexity and its relatives look at the universe as being organismic rather than mechanistic, functioning by means of reciprocal causation, or recursivity. Complexity understands that systems are not reducible - that they are more than the sum of their parts. For example, culture cannot be explained as an amalgamation of individual behaviors, but must be understood as emerging from the relationship between those individuals and, perhaps, other environmental factors as well. The same is true for ecosystems, the body/mind, and other examples of non-linear, recursive systems.
This new epistemology draws together several different lines of thought including Chaos theory (which similarly doesn't exist), cybernetics, systems theory, artificial intelligence, computer modeling, etc. It has given rise to even more lines of thought such as network theory, cellular automata (such as the game of life), genetic algorithms, the new ecology, etc. However, what is most interesting to me is its application in the social sciences and attempts to integrate social theory and environmental studies such as Environmental Anthropology.
Environmental Anthropology and its progenitors (cultural evolution, cultural ecology, ecological anthropology, etc.) have faced numerous critiques over the years. They are said to be deterministic, reductionist, ahistorical, apolitical and any number of other sins. What complexity adds to this is an understanding of the relationships between the members of a society as well as the environmental factors. It rejects the old idea of a "climax ecosystem" and "equilibrium" and views systems dynamically, as constantly changing and emerging. It recognizes the role of accidents of history and differentials of power in the development of the system. It also recognizes that systems that appear stable can collapse at any time - all stability is temporary and elusive. Another benefit of Complexity is the attention to scale and levels of systems. This may make it possible to integrate an understanding of individual actions with institutional behavior - more work needs to be done in this regard. There is a lot of potential here that has yet to be explored, since anthropology hasn't really made any attempt to incorporate Complexity.
That's the best I can do for an explanation right now. I hope it's at least somewhat satisfying, but if you have any questions, feel free to ask. I also recommend reading the above website, and the following books/articles if you're interested in learning more:
Complexity: A Guided Tour
Complexity and Industrial Ecology
A New Ecosystem Ecology for Anthropology
Complex Adaptive Systems, Evolutionism, and Ecology within
Also, as always, anything by Gregory Bateson.
Finally, this blog: Immanence
I may post more later.