There are lots of "little" easy tricks in Photoshop to fix the sky. One easy one is to just do a curves adjustment layer as suggested (click the little half black circle at the bottom of the layers box) adjust the curve until the sky is blue again (don't worry about messing up the lower part). Close the curves dialog and click the mask button at the bottom of the layers box.  Now set the foreground color to black by clicking D and then X on the key board until the foreground indicator shows black. Click B to bring up the brush tool. Set the brush density to about 30%. Click on the mask icon you just created and paint over portions of the photo that you do not wish to be affected by the adjustment layer.  Alternatively, reverse the mask color and paint on the black mask with a white brush. You could also use the gradient tool to "paint" the mask for you.  Sounds complicated as a step by step, but it's not.  Do it once and you'll never look back.

I can swear there ain't no heaven but I pray there ain't no hell. _ Blood Sweat & Tears