You have a long learning curve ahead of you! Open your image with the washed out sky and make a selection of the entire area you want to replace. When that area is selected simply delete the sky. Open the image with the good sky and simply drag that image into the first image. Keep in mind that the images need to have the same resolution. You will also probably need to adjust the stacking order of the layers.

I have been working in Photoshop professionally since version 4 and I still learn something new about it each day. I would suggest spending some time over at the Adobe forums for Photoshop.

Good luck!

The above info is correct, I'm just going to add to it a bit.
When making your selection with the WAND TOOL, keep in mind that it will select a certain amount of colors that are close to the one you selected. To increase or decrease the amount, you will see a value most likely set at the Photoshop default of 32 on the toolbar after you selet the Selection Tool. You can play a bit with this if the wand selects to much or to little. After selecting the sky and you see a few area's that are still not selected, press and hold the SHIFT key to add to your selection. You'll notice a small + sign show up when you press it. ( ALT KEY for minus)
If you already have copied the sky to your clipboard, you may use the Paste Into found under the EDIT in the top toolbar.
There's so much more in PhotoShop than most will ever use, but you have to start somewhere, right?

One of the first things I learned about Photoshop after I became moderately proficient was that there are, more often than not, several ways to solve a specific problem when working with an image. There are several of us at work with me and we often have different ways of doing the same task.