To get started, first we need to select the sky we want to replace. The quickest and easiest way to do this is by using the Magic Wand tool, one of the few situations in which this tool gives good results. With a tolerance of 30 and ensuring that the Contiguous box is checked, click anywhere in the sky area. It probably won't select the whole sky in one go, but by holding down the Shift key and clicking in unselected areas, you can add more to the selection until the whole sky is selected. Don't worry too much about the fine details of the edge, such as tree leaves and such, just as long as the selection is pretty close.
The reason we don't have to worry about the details is because we want to blur or soften the eadge of the selection to make it less obvious. This is called feathering, and you'll find it in the Select menu. Set a value of about five pixels to slightly blur the edge of the selection. Fortunately the feathering in Photoshop Elements is smart, and doesn't affect the edges adjacent to the edge of the image.
Next we need to change the selection so that it's the foreground that's selected rather than the sky. To do this we simply select Inverse from the Select menu, or use the keyboard shortcut Ctrl + Shift + I.