|MadSci Network: Earth Sciences|
A blue sky, on earth or any other planet, is caused by refraction. Red light is bent and scattered less than blue light, so while we see red/yellow coming only from the sun, we see blue coming from all directions!
For the sky to be red, blue light would have to be either completely absorbed or reflected, and only red light allowed through. This can actually happen on earth; at sunrise and sunset we have red skies because the greater depth of air ends up completely absorbing or scattering the shorter wavelengths of visible light.
To see a red sky all around, one would need either a much thicker atmosphere (in which case it's dubious whether any light would get through at all) or an atmosphere rich in compounds which preferentially absorb blue light. It is actually thought, I believe, that Titan may have a red sky due to the high concentration of more-or-less complex hydrocarbons (photochemically generated) in its atmosphere.
Try the links in the MadSci Library for more information on Earth Sciences.