Changing the sky or adding clouds in a photo

[jlovda]

How can I change a washed out white sky in a photo to have a beautiful blue sky with puffy cumulus clouds? Also, if I change a white sky to graduated blue, tall trees are also shifted to blue. How do I just change the sky in the background?

I have attached a screen grab of another photographer's work. Everyone one of his photos look perfect, dozens. He must be using some photo editing software.

Thanks

[migf1]

I can't think of a quick way for those particular photos, because they are quite busy.

I would go with masking the sky first.

The picture to the left is way too busy, but the blue channel of the picture to the right combined with a Levels adjustment gives a nice base for a mask: http://prntscr.com/uy72hp

Using the Brush tool we can complete it, to something like this: http://prntscr.com/uy734s

Next, we copy it into the main image and make it an actual mask from Luminance: https://gyazo.com/aed76c72c161eba53e3eff469773f43c

We can now bring in a new sky as a new layer inside the mask group: https://gyazo.com/e5cd93be3ef14135b4f7459f00a8afcd
and manipulated it further inside the group.

PS. I chose to do it with a mask, because they are non-destructive and allow us to edit them at any given time for fine tuning.