According to the fossil record, species of cyanobacteria fist became numerous in the oceans about 2.7 billion years ago. Nostoc is an extremely fascinating genus of Cyanobacteria which are often called blue-green algae, though they are not all a blue-green color and, in fact, are not even algae at all. The green coloration comes from their chlorophyll while the blue comes from a photosynthetic accessory pigment called phycocyanin. Some cyanobacteria, like Nostoc, have a different accessory pigment called phycoerythrin. This is red and combined with the green chlorophyll gives these cyanobacteria a brown color.
picture by Paul James, click for original site
You can find them in gelatinous colonies all over the place! These are composed of filaments called "trichomes" surrounded by a thin sheath. They are common in both aquatic and terrestrial habitats, and all over the world.