There are signs of life at 3.8 billion years ago, just 700 million years after the formation of the Earth. I've discussed in more detail the advent of eukaryotic life here. The discussion below revolves around multicellular animals, and several discoveries that push back the timeline of their emergence. This ameliorates the picture of Cambrian-period "explosive" evolution, and replaces it with a more steady narrative. As in all paleontological tales, the evolution of understanding is a matter of both further discovery, and finer interpretation of existing evidence.
The first multicellular life (algae) dates back 1 billion years; the first multicellular animals date from 575 million years ago (the sponge-like Ediacarans).
From 542 to 520 million years ago in the Cambrian period was the relatively sudden evolution of more modern animal forms, which has piqued the curiosity of many, including Stephen Jay Gould. Gould explains the difference between Ediacaran animals and modern ones in terms of body layers: the former are diploblastic while the latter are triploblastic, essentially meaning they have an outer layer (ectoderm), a gut (endoderm) and, most importantly, a mesoderm in the middle, which lends the capacity for complex internal organs.
Traditionally, as a central narrative of animal evolution, the Cambrian explosion lacked context. However, more recent discoveries place the ancestors of Cambrian animals much further back, to about 850 million years.
One discovery concerns analysis of the bountiful Doushantuo Formation, a seabed fossil lode from China. Dating from 550 to 580 million years - latter times for the Ediacarans - tiny spheres have been found to be early animal embryos. Hard, spiky shells ruled them out as large bacteria, and those same shells, sans embryo, have been identified from 632 million years, early Ediacaran period.
This finding was reported in 1998 (Xaio, Zhang, and Knoll in Nature), and discussed at length by Gould in Lying Stones Of Marrakesh (notwithstanding his continued maintenance of special significance he previously accorded to the Cambrian).
Going back further, to 635-713 million years ago, a form of cholesterol has been found, 4-isopropylcholestane, now found only in some sponges.
Further: 850 million year old rocks in Canada (MacKenzie Mountains), which contain stromatolites (traces of cyanobacteria), have also been found to have a particular pattern of calcium carbonate which has been identified as characteristic of a collagen mesh, which only animals build. The discoverer (Canadian Elizabeth Turner) says the life form was even more primitive than a sponge: "a few different types of cells living together in a shared, collagenous matrix".
These discoveries fit well with molecular clock calculations: that is, comparative DNA analysis had already put back the advent of animals to about this time frame - yet evidential traces hadn't been identified until now. Others cast doubt on the interpretations of the evidence above, while still accepting animal evolution as dating back further than other evidence has shown.
I think a key aspect of the emergence of multicellular animals is the environmental backdrop. Photosynthetic bacteria started producing oxygen about 2.5 billion years ago, although this did not extend beyond a few metres of the ocean surface. This oxygen had been poisonous to most life to that point, but fostered development of oxygen-tolerating life. Atmospheric oxygen propelled a chain of circumstances resulted in the lower reaches of the ocean being not just anoxic, but also laden with hydrogen sulphide. Although some bacteria thrived in these conditions, the combinations would have been a "persistent brake on eukaryotice evolution" (according to the above Andrew Knoll).
Then came the second "snowball Earth" ice age, which was seen to "reset the chemistry of the oceans" to make life more favourable to multicellular animal forms. Yet conditions at first were more conducive to smaller, soft-bodied organisms - which, over time, changed the balance, perhaps by eating inimicable bacteria. On one interpretation, increased oxygenation was a result rather than a cause of animal evolution - although it makes more sense that they worked in tandem. The same is conjectured for the set of ice ages that occurred around that time: they could have been just as much a consequence of animal evolution (by sucking out carbon when buried) as a cause. It's easy to envisage a slowly oscillating set of equilibria that eventually settled to a higher oxygen, animal-rich, warm Earth - especially as there were no more snowball Earths once larger animals had evolved (notwithstanding subsequent ice ages of smaller scale).
A fascinating narrative, and one that is more appealing than sudden bursts of evolutionary activity. More detail in the New Scientist article below.
References
Gould, SJ (2000): Of Embryos and Ancestors in Lying Stones Of Marrakesh, Vintage, London.
Fox, D & Le Page, M (2009): Dawn of the animals in New Scientist, 2009, 11 July.
