Click here for the answer:
Answering this one took longer than expected, because the answer was not what I thought it would be. In most areas of the Southwest US, black coatings on cliff faces is something called desert varnish, a very thin layer rich in manganese and iron that is thought to be deposited by microbes.
Here, the layer is up to an inch thick, and made of the mineral hematite. The cliffs are the Navajo Sandstone, which originally had a lot of iron. That iron was dissolved, and redeposited as iron rich minerals (hematite and limonite) in openings and porous spots in the sandstone.