Using the Photoshop Shadow/Highlight correction tool is fairly easy. You go to the Image menu, go to the Adjustments section and select Shadow/Highlight. Click the Show More Options box at the bottom, and then start experimentally dragging the various sliders to get the best combination for your picture. If you lighten the shadow too much everything can end up looking washed out. Sometimes if you then move the highlights sliders up you can recover the detail in the sky and other lighter areas. Just experiment until you get a good balance. I found a web site with a nice tutorial to get even fancier:

http://luminous-landscape.com/tutorials/digital-blending.shtml

And this web site shows you what is possible using the official method with Photoshop CS 2:

http://www.luminous-landscape.com/tutorials/hdr.shtml

I followed the Layer Mask method discussed in the first tutorial. I also added a little more warmth and color using the Image/Adjustments/Photo Filter to get the Super Improved version. Here's the steps:

1. Open your too dark image, select all, copy, and paste, thus creating a second layer
2. Click the little eye icon to off in your new layer (in the layers palette), and click the first layer to select it
3. Bring up the Image/Adjustments/Shadow-Highlight and move the sliders until you can see detail in the too dark areas; don't worry about the highlights, we'll fix them next
4. Select your dark layer to make it active, then click the little mask icon at the bottom of the palette, which will create a layer mask chained to the dark layer
5. Now select all in the dark layer, copy, option click on the blank white mask icon and paste; you will now have a black and white mask of the dark layer
6. Go to Filter/Blur/Gaussian Blur and drag the slider to make things fairly blurry; how many pixels it will take to do this will depend on the size of your image--6 pixels on a 1600x1200 pixel image worked fine for me
7. Click on the little eye icon to leave the mask to see the result

I wanted a bit more warmth and color in the foreground, but wanted the sky to stay cool and blue. So I did these additional steps:

1. Selected all, then went to the Edit menu and selected Copy Merged and pasted, thus getting a new layer containing all I had done thus far
2. In this new layer I used the magic wand tool to select the sky
3. Then inverted the selection so all the foreground was selected
4. Went to Image/Adjustments/Photo Filter and selected a warming filter; you can check the color box, then click on the color to make a custom color filter, and you can adjust just how much it is applied by moving the slider

Once you are happy you can flatten and do a Save as, so you don't lose your original in case you change your mind.

Doing something similar in Photoshop Elements 2 is possible, but even more work. After doing all this I brought up Photoshop Elements 3, opened the original too dark image, went to the Enhance menu item and clicked on the Auto Smart Fix function. The result you can see above. Everyone was quite impressed.