The mucus secreted by the bacteria collects grains of sediment, and they are stuck together with calcium carbonate, also from the bacteria. This builds up into the structures seen in certain sea-shore bays. Cyanobacteria use water, carbon dioxide, and sunlight to create their food, and put out oxygen as a by-product.
The ability of cyanobacteria to perform oxygenic photosynthesis is highly significant. Early cyanobacteria in stromatolites are thought to be largely responsible for increasing the amount of oxygen in the primaeval Earth's atmosphere through their continuing photosynthesis. They were the first known organisms to photosynthesis and produce free oxygen. After about a billion years, the effect of this photosynthesis began to a huge change in the atmosphere. The process, called the Great Oxygenation Event, actually took a long time. Eventually, it killed off most of the organisms which could not live in oxygen, and led to the kinds of environment we know today, where most organisms use and need oxygen.
- from Greek strōma, mattress, bed, stratum, and lithos, rock
- Knoll, Andrew H. 2004. Life on a young planet: the first three billion years of evolution on Earth. Princeton, N.J. ISBN 0-691-12029-3
- For a description of the method used to establish this date, see J. William Schopf 1999. Cradle of Life: the discovery of Earth's earliest fossils. Princeton U. Press (pages 87-89 and figure 3.9). The remarkable precision was possible because the fossils were sandwiched between lava flows that could be precisely dated from embedded zircon crystals.
- Frei R. et al 2009. Fluctuations in Precambrian atmospheric oxygenation recorded by chromium isotopes. Nature 461 (7261): 250–253. Abstract: 
- Heinrich D. Holland: The oxygenation of the atmosphere and oceans. In: Phil. Trans. R. Soc. B, vol. 361, 2006, p. 903–915 http://rstb.royalsocietypublishing.org/content/361/1470/903.full.pdf