I need to address another point, the possibility of there being a limit to the organizational complexity of life. There's a distinct possibility of this being the case. Of the procaryotic organisms alive today, there are only two main divisions, bacteria and archea. There's almost certainly many more types of metabolism or microstructures, or cell wall chemistry that are possible, but only these two versions have survived to the present, if any others ever existed at all.
Earth is a fairly big planet, and it contains a huge number and variety of potential habitats and hazards. If life has become ubiquitous and robust, then there might be rare opportunities for some event leading to a transformation of structure in some lineage, as happened with the origin of eukaryotes. It's conceivable that some worlds might be smaller or simpler than Earth, and the space for major transformations never happens. If life is found to exist in Europa's ocean, it shouldn't surprise us if we find it to be no more complex than our bacteria. But neither should we be surprised if it's gone beyond that.
How about multicellularity? Not necessarily a given, of course, but if that stage is reached, does that mean that life forms will keep becoming more complex? One thing that makes it hard to determine is the definition of complexity itself, as Michael points out, it can be tough to separate this from specialization. It's possible to argue that humans are really no more complex than gorillas -- just different. We contain the same organ systems, very similar DNA, and even a large number of similar behaviors. We do have different specialties. With closely related species, it's hard to find much difference in relative complexity. But over time, these changes become easier to detect. When we go back to the Cambrian explosion, some 540 million years ago, when all the prototypes of the current phyla were taking form, complexity was across the board less than it is today. The common ancestors of annelids, molluscs, arthropods, echinoderms, and chordates were fairly simple, wormlike creatures. Each of these phyla has increased its complexity by embellishing new features on top of the old. Each of these lineages did it independently. Chordates did not trigger complexity in insects.The same phenomena occurred in plants. Once vascular plants began to colonize the land as simple moss-like organisms, they exploded both in diversity and complexity.
None of this is a one-off. There's not a lack of data here, there's a wealth of it. The evidence remains that as different groups of plants and animals evolve, they don't usually gain complexity, and they don't usually lose it, but sometimes they will do both. Since there are a lot more simple organisms than there are complex ones, the loss of complexity in one particular branch doesn't have much effect on the overall complexity of life, but an increase in complexity might. The effect is that the maximum complexity in a population will increase, even if the vast majority of species remain simpler. And if that increase in complexity comes with greater evolutionary sophistication, and a survival advantage, then that more complex clade will begin to diversify on it's own, and give rise to similarly complex relatives. At some point the process will repeat itself. Some lineages in that group will delete features, most will remain similar to the founder, and maybe one will add another embellishment to the existing body structure or behavior. Then the overall level of biological complexity on the planet goes up again. Then the real question is, at what point are the complex members of the group the foundation for further evolution, or to what extent are they dead-end outliers? I don't think you can tell, except in hindsight. But hindsight shows us that there has been a broad, although not steady, increase in the complexity of life over time.
It's very hard to find increases in modern biological complexity, simply because life has already become so complex, and the amount of variation that can occur without a corresponding increase in complexity is vast. But, the fossil record shows that it has occurred, in numerous lineages, throughout geologic history. It wasn't a one-time event, and there's no reason to expect it not to continue from time to time. Not inexorably, not continuously, and not predictably. But as time goes on, as evolution leads to the slow accumulation of features, there continue to be more ways to become more complex than there are ways to become simpler.
Will it last forever? Of course not. Michael mentions periods in Earth's history when overall diversity has decreased. While previous mass extinctions reduced diversity, they didn't lead to much if any reductions in complexity. Specialists tended to become extinct at the highest rates, but generalists can be just as complex as the specialists, and those that survive become the evolutionary raw material for further specialization and diversification. Specialists that don't go extinct, can themselves give rise to more generalist descendents if the competition around them suddenly decreases. It's highly likely that the first creatures with feathers were specialists, and feathers were a novel, specialized feature themselves. When that feature became hugely successful, its owners could spread, adapt, and give rise to more generations of generalists and specialists.
It's true that you can't necessarily extrapolate all of this to any given extraterrestrial planet. But merely the fact that evolution allows for increases in complexity is a good indication that in environments where there is room for more sophisticated organisms, eventually that sophistication will appear. The dynamics of variation, selection, and common ancestry powers that trend, and there's no reason why it shouldn't work anywhere that evolution itself works.