The upper elevations of the mesa tops is known as the Red House cliffs. The base of the cliffs are made of the Permian Organ Rock shale while the mesa top is capped with Triassic Moenkopi and Chinle formations. These red beds indicate bright oxidized muds from the Ancestral Uncompaghre uplift to the east. The drainage at the time making large alluvial fans that filled this part of Utah.
Below the red beds of the Organ Rock/Moenkopi/Chinle lies my second favorite rock unit on the Plateau: Cedar Mesa sandstone. Being as this is the type area, the Cedar Mesa sandstone makes up the majority of Cedar Mesa. Almost every canyon is cut into this very thick white Permian sandstone. The sandstone shows obvious large scale crossbeds and a uniform grain size suggesting wind blown deposits. You can see the crossbedding in the space below the granary. I have read a petroleum description that this is a wet eolian deposit. This is in keeping with the idea of a cyclic rising and falling of local sea level.
Under the Cedar Mesa is the Elephant Hill Limestone . This is one of those limestones I enjoyed using as a prop in intro geology labs. Its a sandy limestone more than a limy sandstone. There are fossils present and samples will do all the things limestone should do in field tests.
So for about 80 million years you can see regime changes happening; seas coming and going all the time. Now this area is very arid region. If the regime was different, lets say similar to the East coast, so much of the existing rock would have eroded away and these magnificent canyons would be nothing but a flat plain.