This is a good time to consider the relevance of the term "behavioral complexity". How is this different from intelligence? How is it the same? Well, intelligence tends to be a relative, subjective term . . . Wouldn't you agree? So, perhaps it is necessary to discuss behavioral complexity when comparing across a number of species. Indeed, the "intelligence" that I need to get through life is different than the "intelligence" a mouse needs. But are my behaviors any more or less complex than a mouse's? That may be where there is the most room for discussion, observation, and scientific study.
Evolutionarily speaking, scientists agree that organisms seem to have become more complex behaviorally. Some argue that this is correlated with increased brain size. Changes to the brain have occured at specific structures, for example the neocortex, not simply with overall brain size. Go to this website for a more in-depth look: "Brain Size and Evolution".
Another method for observing evolutionary trends is to look at the components of the human brain (as an example of a highly "evolved" and "intelligent" species) and trace the function evolutionarily. For example, we can first compare it with a reptilian brain (an example of a less "intelligent" organism). I did this in a picture form on another page. If we look at a reptilian brain we see structures that are observed in the human brain stem and cerebellum. In reptiles the brain stem and cerebellum dominate, as these parts of the brain control balance, vital life functions (breathing, heartrate), and movement.
The next component of the human brain to explore is the limbic system. Some scientists refer to this as the "paleomammalian brain". In other words, this part of the brain corresponds to the brain of most "early" mammals. The function of the system is predominantly emotion, instincts, hunger, fighting/fleeing, memory, sensory input, and sexual behavior.
Finally, the neocortex is assumed to be the superior ("neomammalian") part of the brain, which makes up the majority of the cerebral hemispheres. Species which are considered to be highly intelligent, such as humans and dolphins, tend to have large amounts of neocortex. This structure is assumed to be responsible for higher cognitive functions and is associated with greatest behavioral complexity. While all mammals have a neocortex, some (for example: a mouse) have less cortical folding than others (for example: a human). Interestingly enough, a mouse whose cortex has been highly lesioned can act in a relatively normal way (superficially) while a human without a cortex is essentially non-functioning.
This is an interesting representation of the "Triune Brain" hypothesis: