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 expel oxygen as a by-product.
The real significance of stromatolites is that they are the earliest fossil evidence of life on Earth. The oldest known stromatolites have been dated between 3,710 million years and 3,695 million years old, and were discovered from an exposed outcrop of metacarbonate rocks in the Isua supracrustal belt (ISB) in Southwest Greenland. The ISB stromatolites predate by over 215 million years the previous most convincing and generally accepted multidisciplinary evidence for oldest life remains: stromatolites in the 3,480 million year old Dresser Formation of the Pilbara craton in Western Australia.
At one time, the oldest known stromatolites were dated to 3,450 million years ago, during the Archaean eon, but the more recent discoveries of older stromatolites provides evidence in accord with genetic molecular clock studies that have placed the origin of life in the Hadean eon.
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 make 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
- Nutman, Allen P.; Bennett, Vickie C.; Friend, Clark R. L.; Kranendonk, Martin J. Van; Chivas, Allan R. (2016/09). "Rapid emergence of life shown by discovery of 3,700-million-year-old microbial structures" (in En). Nature 537 (7621): 535–538. doi:10.1038/nature19355. ISSN 1476-4687. http://www.nature.com/doifinder/10.1038/nature19355.
- VANKRANENDONK, M; PHILIPPOT, P; LEPOT, K; BODORKOS, S; PIRAJNO, F. "Geological setting of Earth's oldest fossils in the ca. 3.5Ga Dresser Formation, Pilbara Craton, Western Australia". Precambrian Research 167 (1-2): 93–124. doi:10.1016/j.precamres.2008.07.003. https://doi.org/10.1016/j.precamres.2008.07.003.
- 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.
- Hedges, S. Blair (2002/11). "The origin and evolution of model organisms" (in En). Nature Reviews Genetics 3 (11): 838–849. doi:10.1038/nrg929. ISSN 1471-0064. http://www.nature.com/articles/nrg929.
- 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