I think this works pretty well for a quick fix
http://www.pbase.com/image/35249975.jpg

Open image of cloudy sky and resize as appropriate
Move cloud picture onto the tree image
(1)Change the new layer to Darken and
(2)open a black layer mask to hide the sky layer.
(Alt+layer mask icon at bottom of layer palette)
Use white brush to reveal cloudy sky.
Sky layer won't show over the dark background trees so overlapping brush won't hurt.
Retouch any incidental darkened areas in the bright yellow foliage with a white brush.
(3) Make final adjustment to layer opacity if necessary to soften sky and minimize visible artifacts
--
Joe Filer
Mahomet, IL
My stuff:
http://www.pbase.com/image/33486685