You need 2 pictures: The one that you have with the drab sky which you wish to replace, and a picture of a "good" sky - just blue sky with clouds, nothing else on it. You can take the picture of the sky yourself, or download one from another source.
Also, familiarize yourself with the gradient tool, as we will be using this in step #7.
- Open your picture (A) (File>open), and open the replacement sky picture (B)
- On the sky picture (B), go to Select>all from the menu, then Edit>copy to place it on the clipboard
- Go back to your picture (A), then Edit>paste. The new sky (B) should come in on a new layer
- With the move tool, use the corner handles to reduce the size of the sky (B) to cover the old sky on (A)
- In the layers palette, set the blending mode of (B) to darken
- Set the foreground color chip to white
- Get the Gradient tool out of the toolbox, and drag a foreground to transparent, linear gradient from below up to the top of the tree line, while holding down the shift key.