Start by making a new Curves Adjustment Layer. Holding the option key on a Mac, or alt key on a PC, click on the black/white circle at the bottom of the Layers Palette, and choose Curves.
You can then name your adjustment layer. This is a good idea, so that you can keep track of what you're doing. I'm going to start by working on the sky, so I've named my layer "sky".
Once you've done that, your Layers Palette will look like the one here. On the bottom you've got your image, and above that the Curves adjustment layer.
There are two boxes in the Curves Adjustment Layer. The one on the left will open the curves if you double click on it. The one on the right is the Layer Mask. It starts out white, which means that the adjustments you make will affect the entire image.
We'll set the curves values before we mask it out. Double click on the curves box on the sky layer (remember, that's the one on the left).