The ancient Greek philosophers tried to use their logical and argumentative abilities to summarize the workings of the world in terms of a few concepts. Sometimes this natural philosophy led to surprisingly accurate deductions, such as Democritus' argument that matter at the microscopic level must eventually be indivisible, leading him to the concept of atoms. However more often than not, the natural philosophies were misleading or wrong: A dropped stone fell straight to the ground because "that was its natural state", whereas a feather fell much slower and in an erratic manner "because that too was its nature."
It would take many years before Galileo would argue that both the stone and feather would fall at the same rate, and straight down, once wind and air-resistance were neglected. This was a very important development because it illustrated that things can be simple if we focus on simple things! : Controlled experiments are done where only those factors one is interested in studying are allowed to vary while the rest are kept fixed. Such controlled experiments are idealizations of natural phenomena and are meant to uncover the basic underlying rules of how the world works. The use of controlled experiments, and the scientific method of comparing hypothesis and theoretical predictions with experiments, has been the key to the success of the natural sciences.
By uncovering the few fundamental laws behind diverse phenomena, the world appeared to become more understandable and simple. With regard to the example above, Newton later showed that not only did the stone and feather fall to the earth at the same rate, so did the moon: the law of gravitation is universal. This universality of fundamental laws is what makes us believe in the ultimate simplicity of the world.
The approach to understanding a phenomenon that begins by looking for the basic constituents of the system under investigation, and deducing the consequences of the simple fundamental laws that govern their interaction, is called reductionist. This approach has been immensely successful not only in the physical sciences but also in some sub-disciplines of the live-sciences such as molecular biology. However there are many interesting phenomena that cannot be easily understood using the reductionist approach. For example, although the DNA code tells us much about an organism, it is in practice impossible to describe all the functions and behaviour of the organism from this viewpoint. The reason of course is simply that the system of interest has complex interactions among its very many constituents. (Recently the whole human genome was decoded, revealing that we have far fewer genes that previously thought, in fact only a few more than other simple organisms. Our complexity thus comes not simply from the single detailed code, but probably from interactions among the various genes or the proteins that they encode.)
Consider the simpler example of a water molecule: With sufficient effort, a physicist can deduce its properties from the rules of quantum mechanics. However, deducing the properties of water vapour already becomes a computationally intractable problem in the first principles approach because of the exponentially large number of molecules involved. Nevertheless the problem is still manageable in a statistical treatment if the system is in equilibrium. Indeed, statistical mechanics is the old science of complexity, developed for the description of closed systems in equilibrium that are describable by a few macroscopic degrees of freedom such as temperature and pressure. Therefore at least in some cases, large complicated systems can be understood by supplementing the reductionist approach, that is the deterministic underlying laws, with the methods of probability and statistics.
Yet, most interesting phenomena in nature are actually open, non-equilibrium systems in which there is a continual inflow of matter, energy or information and also dissipation. It is such systems that are nowadays referred to as 'complex'. The field of study called 'Complexity' concerns itself with obtaining common global perspectives of systems, consisting of very many interacting constituents, which cannot be easily described by a few effective degrees of freedom. These systems are usually out-of equilibrium and mathematically described by nonlinear equations. For example, water draining in a bathtub forms a complicated dynamically ordered object --- the vortex. Some other examples are earthquakes, river networks, the economy, and biological systems.
Other than dynamical order, complex systems very often display patterns or spatio-temporal correlations --- fractals, 1/f noise, power laws. That is, very simple emergent laws (usually statistical, as opposed to the underlying fundamental laws) often arise from collective effects and operate at the macroscopic level of a complex system. Understanding these observed regularities, at least qualitatively, is the purpose of a theory of complex systems. Thus the goal of complexity studies is the direct opposite of the field of chaos: In chaos one tries to understand the complicated behaviour of simple systems ('things can be complicated even when they are simple'), whereas in complexity one seeks to understand the emergence of simple patterns and order in large complex systems: That is, why things can be simple even when they are very complicated!
One can summarise the various philosophies as follows. "Conventional Wisdom": Simple systems have simple descriptions, that is, the fundamental laws are simple and if things look complicated it is only because they have not been analysed down to their basic constituents (reductionism). "Chaos": Things can get very complicated even in simple systems (the world is full of surprises). "Complexity": Very large complex systems can sometimes display remarkably simple regularities, that is, patterns, order and simple statistical laws can emerge unexpectedly. In other words, relative simplicity of the underlying rules can lead to complexity when the number of agents is large, but then one often has simplicity again in the emergent properties that arise.
It is important to note that there is no single theory of complex systems, but rather a number of useful concepts and principles that allow a common understanding and description of some features of a variety of different systems. The understanding and 'explanations' thus obtained are, for the most part, qualitative and as such their value is more for developing intuition, constraining possibilities statistically, and in seeing the 'big picture'.