There are a number of ways to approach the concept of complexity, none, I think, inherently any better than any other.
A simple cybernetics approach would simply count the number of parts, the number of types of parts and the number of types of relationships between the parts of the system. Game theory would view those relationships as rules which govern the parameters of the game and which in turn constrain the strategies of the causal parts of the system, called players in the game. General systems theory would go a step further, applying the cybernetic approach within the system itself and applying the game theory approach towards the system interacting with it's larger context environment (psychology within sociology, sociology within ecology, etc.).
But these are older perspectives. The newer nonlinear-dynamics folks, as characterized by the Santa Fe group, would be more likely to start with an information theory perspective of complexity. If you're tring to measure the complexity of a given system, you would speak in terms of it's compressability. In other words, to how simple an alogorithmic description of the system can you reduce it while still doing the phenomena justice? If it's a simple repeating pattern adequately captured by a linear equation, then it's not very complex. This view has the interesting consequence that purely random signals are incredibly complex.