This took at most a minute and a half.
All of my sky images are landscape orientation; I didn't figure it would look very good if a rotated the sky to portrait mode; so, I used Image > Transform > Free Transform to drag the sky tall enough to fit.
I didn't take any pains in choosing the sky; I just grabbed the first one in the folder.
As you can see from the layer stack, I used a Brightness/Contrast adjustment layer to darken the little limbs and leaves = Brightness -60 Contrast +28
To lessen the effect on the main trunk, I painted over it on the layer mask with Medium Grey.
On the Sky layer, I set the blend mode to Darken and Opacity to 63%
Then, to really make it "Pop", I used NIK > Color Efex Pro > Landscape > Pro Contrast with the Correct Contrast slider at 30% and Dynamic Contrast at 100%
Other than the NIK, which is a free Elements Plug-in, everything was done with in-house Elements 7.
I just wanted to show that, so long as your foreground elements are darker than the sky, you don't have to do a bunch of meticulous selecting to blend on a new sky; it is the Darken blend mode and playing with the opacity that does the trick.
The sky is a photo that I purposefully took myself to add to my growing collection of sky photos.
I hope this helps.
