It may seem surprising that bacteria can leave fossils at all. However, one particular group of bacteria, the cyanobacteria or "blue-green algae," have left a fossil record that extends far back into the Precambrian - the oldest cyanobacteria-like fossils known are nearly 3.5 billion years old, among the oldest fossils currently known. Cyanobacteria are larger than most bacteria, and may secrete a thick cell wall. More importantly, cyanobacteria may form large layered structures, called stromatolites (if more or less dome-shaped) or oncolites (if round). These structures form as a mat of cyanobacteria grows in an aquatic environment, trapping sediment and sometimes secreting calcium carbonate. When sectioned very thinly, fossil stromatolites may be found to contain exquisitely preserved fossil cyanobacteria and algae.
The picture above is a short chain of cyanobacterial cells, from the Bitter Springs Chert of northern Australia (about 1 billion years old). Very similar cyanobacteria are alive today; in fact, most fossil cyanobacteria can almost be referred to living genera. Compare this fossil cyanobacterium with this picture of the living cyanobacterium Oscillatoria:
The group shows what is probably the most extreme conservatism of morphology of any organisms.
Aside from cyanobacteria, identifiable fossil bacteria are not particularly widespread. However, under certain chemical conditions, bacterial cells can be replaced with minerals, notably pyrite or siderite (iron carbonate), forming replicas of the once-living cells, or pseudomorphs. Some bacteria secrete iron-coated sheaths that sometimes fossilize. Others may bore into shells or rocks and form microscopic canals within the shell; such bacteria are referred to as endolithic, and their borings can be recognized all through the Phanerozoic. Bacteria have also been found in amber -- fossilized tree resin -- and in mummified tissues. It is also sometimes possible to infer the presence of disease-causing bacteria from fossil bones that show signs of having been infected when the animal was alive. Perhaps most amazing are the fossils left by magnetobacteria -- a group of bacteria which form tiny, nanometer-sized crystals of magnetite (iron oxide) inside their cells. Magnetite crystals identifiable as bacterial products have been found in rocks as old as two billion years -- at a size of a few hundred millionths of a meter, these hold the record for the smallest fossils.
Bitter Springs chert fossil image provided by J. William Schopf. The image of Oscillatoria was provided by Alejandro Lopez-Cortes (CIBNOR, Mexico), Mark Schneegurt (Wichita State University), and Cyanosite.