The first order of business is to clean the stone of living & dead matter before we can begin to add the sealing compound. There are several approved mixes of biodegradable substrates that are approved to use as often as once every 5 years. The substance is coated onto the stone and a black plastic bag is then put over the stone to finish killing the living matter on the stone. A simple deviation of this is to add a black plastic bag over the stone for a couple of months and the living matter and stains will disappear, because most of that is living matter which will die without light and air. Any remaining stain can be washed away with water. Remember all plants need light water and air to remain healthy. Deprived of any one of those and the lichens and mosses that cling so easily to the stone will die and fall off. Care should be taken so as to avoid cleaning with detergents that contain compounds like sodium bicarbonate (baking Soda), sodium chloride (Salt), sodium sulfate, ammonium carbonate, and tri-sodium phosphate. You can prepare a homemade poultice by mixing equal parts of water and vegetable glycerin (actually used in skin care) in dry porcelain clay until you get a smooth consistency. after application and use any of these compounds should be flushed thoroughly afterward to remove any residue.

An example of a non-ionic cleaner which can be safely used to clean headstones. Use with lots of water afterward.

A approved approach to sealing old cracked monuments which are found in many old graveyards is to use an approved mix of 2 parts white Type N mortar white concrete mix. The white concrete mix is hard to find and expensive. I am told by concrete manufacturers that Type N mortar mix which comes in a gray color could be substituted, but don't tell Dan Sumner Allen IV President of Cumberland Research Group. HA! It is the same chemical composition, but is gray in color. Add to that 4 parts of (white) Hydrated Lime purchased from any concrete supply store and then add 8 parts white sand. Children's' play sand is good because the color is lighter, it is finer, and is not made of crushed glass to break your hands out. Mix all that together in the volume needed and add water and mix until it becomes a soupy mix in your mixing container.
Of course stir the mix until it is thoroughly blended and a bit on the slushy side. After putting on your rubber gloves gather up a handful of the mix and smear it across the face of the stone into the cracks and then all over the stone being sure it is pressed into the cracks and crevices. Do a good job here because this part is very critical to the success of the effort. You should notice it is filling all the small cracks if you are doing a good job and have added the right amount of water to the mix . If there is a large crevice somewhere on the stone then use the mix in thicker form to fill the crevice with more of a solid material. Next let the applied stone dry for a few minutes then with a common garden sprayer filled with common water and  pumped up gently wash the surface of the stone to be sure you clear any residual matter inside the inscription and other places the material may have become too concentrated.
You may be be sure this procedure will continue to allow water to seep into the stone and run thru its porous surfaces, but it slows down that process. Allowing the water to seep into the stone and not becoming trapped so that the heating and cooling of the stone occurs in an even matter based on having the same level of moisture inside the contents of the stone at all times. This is key to keeping the stone healthy long term. Sealing the stone is a misnomer as we never want to technically seal the stone and prevent it pores from allowing water to exit its content.

This stone for Rezin Smith b. 1787-1851  found in the Richmond Cemetery in Bedford County Tennessee is a typical example of a stone that will benefit from cleaning and sealing with the above procedures. Notice some living stains are reddish in color and others brownish. The main face of the stone has blackish mold on it. Any unapproved methods of sealing a stone is unacceptable and will do more harm than good in the long term.

Do not use any of the following:
(1) Commercial Concrete sealer as found in the hardward store. (2) Deck Sealer. These products or any others will cause the stone to retain water in varying amounts at different places on the stone. This varying retention sets up the stone for damage from heating and expansion and drying in the elements of nature.

Added 20 Jul 2015, based on the teachings of Dan Sumner Allen owns & runs a Professional cemetery maintenance company.