Color, generally, is ascribed with ser. In the mental model I'm assembling as I learn Spanish, this seems to be because it is, generally, a durable characteristic. El cielo es azul - the sky is blue.
What is the correct verb for a temporary color that reflects a state? For example, 'the sky is grey'. Is it el cielo es gris, because it's a color, or el cielo está gris, because the color is being used to describe a present state? Or is that kind of construction not used?
When is a temporary state use está
El cielo está gris.
For durable state use es
El cielo es azul
Excelent explanation related: Why do we say "Qué hora es" instead of "Qué hora está"?
The particular question about colors is already answered correctly.
When you say the sky is gray, you are pointing to a changing state, so it's estar. You can say "El cielo es celeste" (or "azul"), but with the meaning that blue is the (real) color of the sky. There's a little subtle difference. Most of the time you'll be talking about how the sky is now.
When you speak about things that don't change color, use ser. "Las rosas son rojas", "El auto es verde".
About the difference between both verbs, I wanted to add my two grain:
As stated before, the general rule to distinguish between both verbs is if you refer to something transient (estar, think status) or permanent (ser).
But then, this is subject to interpretation, plus some "quirks" that language evolution introduces over time. It's not as regular and logical as we (native Spanish speakers) tend to see it.
There's a nice article in Wikipedia (in English) I recommend you to read for the theoretical side:
http://en.wikipedia.org/wiki/Romance_copula
For the practical side, I guess it's just study, practice, perseverance, and some help.
This is one common problem to english speakers when learning spanish.
While in english you use "to be" as the same verb for defining states, on spanish we use two different verbs, "ser" y "estar", with "ser" as a verb wich implies a fixed or adquired state while "estar" implies some type of "transitivity".
An example. On english you could say: Peter is a software developer, he is working at Nokia.
While on spanish this phrase would be: Pedro es desarrollador de sofware, está trabajando para Nokia.
So, Peter's condition is to be (SER) a software developer, while it's current situation is again to be (but ESTAR on spanish) working at Nokia.
