Bacteria appeared on Earth at least 3.5 billion years ago, only a few hundred million years after the Earth cooled to the point at which living creatures could survive on it. We know this because of strange layered structures found in sedimentary rocks. The layers can be flat and bumpy, they can form huge branched pillars, or they can be highly convoluted like the leaves in a cabbage. Some deposits are half a mile thick and spread for hundreds of miles. Most date from 2 billion years ago, but those from Warrawoona in Australia are 3.5 billion years old.
To begin with, nobody knew what these deposits were, In the 1950s and 1960s they were revealed as traces of communities of bacteria, especially cyanobacteria.
Cyanobacteria collect together in shallow water to form huge, floating mats, like felt. They secrete a sticky gel as protection against ultraviolet light, and this causes sediment to stick to the mats. When the layer of sediment gets so thick that it blocks out the light, the bacteria form a new layer, and so on. When the layers fossilize they turn into stromatolites, which look rather like big cushions. The wizards haven't been expecting life. Roundworld runs on rules, but life doesn't, or so they think. The wizards see a sharp discontinuity between life and non-life. This is the problem of expecting becomings to have boundaries, of imagining that it ought to be easy to class all objects into either the category 'alive' or the category 'dead'. But that's not possible, even ignoring the flow of time, in which 'alive' can become 'dead', and vice versa. A 'dead' leaf is no longer part of a living tree, but it may well have a few revivable cells.
Mitochondria, now the part of a cell that generates its chemical energy, once used to be independent organisms. Is a virus alive? Without a bacterial host it can't reproduce, but neither can DNA copy itself without a cell's chemical machinery.
We used to build 'simple' chemical models of living processes, in the hope that a sufficiently complex network of chemistry could 'take off', become self-referential, self-copying, by itself There was the concept of the 'primal soup', lots of simple chemicals dissolved in the oceans, bumping into each other at random, and just occasionally forming something more complicated. It turns out that this isn't quite the way to do it. You don't have to work hard to make real-world chemistry complex: that's the default. It's easy to make complicated chemicals. The world is full of them. The problem is to keep that complexity organized.
What counts as life? Every biologist used to have to learn a list of properties: ability to reproduce, sensitivity to its environment, utilization of energy, and the like. We have moved on. 'Autopoeisis', the ability to make chemicals and structures related to one's own reproduction, is not a bad definition, except that modern life has evolved away from those early necessities. Today's biologists prefer to sidestep the issue and define life as a property of the DNA molecule, but this begs the deeper question of life as a general type of process. It may be that we're now defining life in the same way that 'science fiction' is defined, it's what we're pointing at when we use the term.
The idea that life could somehow be self-starting is still controversial to many people. Nevertheless, it turns out that finding plausible routes to life is easy. There must be at least thirty of them.
It's hard to decide which, if any, was the actual route taken, because later lifeforms have destroyed nearly all the evidence. This may not matter much: if life hadn't taken the route that it did, it could easily have taken one of the others, or one of the hundred we haven't thought of yet.
One possible route from the inorganic world to life, suggested by Graham Cairns-Smith, is clay. Clay can form complicated microscopic structures, and it often 'copies' an existing structure by adding an extra layer to it, which then falls off and becomes the starting point of a new structure. Carbon compounds can stick on to clay surfaces, where they can act as catalysts for the formation of complex molecules of the kind we see in living creatures, proteins, even DNA itself. So today's organisms may have hitched an evolutionary ride on clay.
An alternative is Gunther Wachterhauser's suggestion that pyrite, a compound of iron and sulphur, could have provided an energy source suitable for bacteria. Even today we find bacteria miles underground, and near volcanic vents at the bottom of the oceans, which power themselves by iron/sulphur reactions. These are the source of the 'upflow of poisonous minerals' noticed by Rincewind. It's entirely conceivable that life started in similar environments.
A potential problem with volcanic vents, though, is that every so often they get blocked, and another one breaks out somewhere else. How could the organisms get themselves safely across the intervening cold water? In 1988 Kevin Speer realized that the Earth's rotation causes the rising plumes of hot water from vents to spin, forming a kind of underwater hot tornado that moves through the deep ocean. Organisms could hitch a ride on these. Some might make it to another vent. Many would not, but that doesn't matter -all that would be required would be enough survivors.
It is interesting to note that back in the Cretaceous, when the seas were a lot warmer than now, these hot plumes could even have risen to the ocean's surface, where they may have caused 'hyper-canes', like hurricanes but with a windspeed close to that of sound. These would have caused major climatic upheavals on a planet which, as we shall see, it not the moderately peaceful place we tend to believe it is.
Bacteria belong to the grade of organisms known as prokaryotes. They are often said to be 'single-celled', but many single-celled creatures are far more complex and very different from bacteria. Bacteria are not true cells, but something simpler; they have no cell wall and no nucleus. True cells, and creatures both single-celled and many-celled, came later, and are called eukaryotes. They probably arose when several different prokaryotes joined forces to their mutual benefit, a trick known as symbiosis. The first fossil eukaryotes are singe-celled, like amoebas, and appear about 2 billion years ago. The first fossils of many-celled creatures are algae from 1 billion years ago ... maybe even as old as 1.8 billion years.
This was the story as scientists understood it up until 1998: animals like arthropods and other complex beasts came into being a mere 600 million years ago, and that until about 540 million years ago the only creatures were very strange indeed, quite unlike most of what's around today.
These creatures are known as Ediacarans, after a place in Australia where the first fossils were found. They could grow to half a metre or more, but as far as can be told from the fossil record, seem not to have had any internal organs or external orifices like a mouth or an anus (they may have survived by digesting symbiotic bacteria in their selves, or by some other process we can only guess at). Some were flattened, and clustered together in quilts. We have no idea whether the Ediacarans were our distant ancestors, or whether they were a dead end, a lifestyle doomed to failure. No matter: they were around then, and as far as anyone knew, not much else was. There are hints of fossil wormcasts, though, and some very recent fossils look like ... but we're getting ahead of the story. The point is that nearly all Ediacaran life was apparently unrelated to what came later.