First things first, the use of a graphic tablet is a must for this tutorial. This tutorial is made in CS3 but for most older versions of photoshop there shouldn't be a problem because the tecnniques used are scarce.
The main tools used are gradient tool and smudge tool.
Good luck and have fun!

Make a new file with the dimensions width 1280px and height 800px.
Use the colorpicker tool to collect colors from a photo or painting, this helps to get a more realistic feel to the end result. Blurring a photo or using the filter paint daubs with a large brush size and sharpness 0 helps to get the colors. I marked the places where I took the colors. Don't just click anywhere, use the darkest blue from the sky, the colors which give depth to the picture and some foreground colors.

Use the gradient tool to set the colors for the background. Use three of the colors you have just picked.
The darkest blue from the sky, the lighter white/gray also from the sky and a color from the foreground.

Make a new layer for every new object, very useful when you need to change or add things to the illustration in a later stage.
Add a new layer.
Select the polygonnal lasso tool and use it to make the outlines for the mountains in the background as shown below.
Now select the gradient tool and fill the new shape with the two colors shown on the right. The mountaintops should be a bit darker.

Make the remaining three layers of mountains the same way as desribed in the previous step.
Use the polyganol lasso tool and fill the layer using the gradient tool.
Use the colors you picked from your reference image.
Don't forget that the mountaintops should be a bit darker, this is done to create a fog effect at the foot of these mountains.

Make the lake, the rocks and the foreground the same way as you made the mountains. Be creative about the shapes, there are endless posibilities.
After you are done making the shapes, flatten the four layers with the background mountains into one layer. Also flatten the lake, the rocks and the shapes that make up the foreground into another layer.
Name the layers, "background", "mountains" and "foreground". Always name your layers, so when you have a complicated file with lots of layers it's much easier for yourself but also for someone else to see how the image is build.

Make a lightsource coming from the right.(By choice you could make it come from the left.)
Set the foreground color to white.
Use the gradient tool, set to "foreground to transparent", the mode should be "color dodge", the opacity setting on a low value, I chose 12%.
Select the layer "background".
Click on the rightside in the middle of the image and drag the pointer to the center of the image, release at that center.
Now select the layer "mountains" and again drag the pointer to the center of the image and release.

Use the smudge tool to create details in the most distant mountainline, set the diameter to a low value. I used a setting of 4 pixels. If you use a smaller diameter you can give the image more detail.
You can activate the option "Finger Painting" for different kind of effects.
Start smudging with a lot of pressure from just above the mountaintops in a bend or corner down and to the right untill just above the next line of mountains. Smudge these strong lines into the mountain ridges. What you are actually doing is smudge away parts of the mountains so the background color can shine through. You can hide the background layer to see the effect.
Do the same for the three remaining groups of mountains.
Keep in mind that the light is coming from the right, and that the darker mountains are much closer that the faint colored mountains.
And don't worry if the effects that you achieve are not what you expected, it takes some practise. I always tip people to look at real pictures of the subject you want to draw as a reference.
In the next step there is a more detailed explanation of how to smudge the mountains into shape.

Smudging the mountaintops: Smudge in the direction of the red arrows.
Darker red means more strength.
Smudge diameter is set to 4 pixels, option Finger Painting is selected.

Use the same technique when smudging the foreground into shape, but set the brush diameter a bit larger to 6 or 8px.
Also select the option "sample all layers". This means that you can smudge the color from the background into the foreground layer without distorting the background layer. This option could also have been set when smudging the background mountains to get a different effect.
Don't forget about the lightsource, and start smudging down from the corners with a lot of pressure.

Use the same technique for the water and the rest of the foreground, but this time when smudging make a lot of "uncontrolled" movements like circles and twisted lines.
Use a diameter between 2 and 8px. Use the smaller brush to create more details.

Now let's make some clouds.
First make a new layer, call it "clouds" and put it behind the mountains layer and over the background layer.
Select the brush tool and change the brush tip to "dry brush".
This brush should be a standard brush in CS3, no need to change the brush palet. If you are using a different version of photoshop and can't find it, you could just select a similar type of brush.
Bring up the brushes window using F5, the standard menu button or using the menu=>window=>brushes option.
Make sure that the settings are as below, don't forget to adjust control settings to "pen pressure".

Start with a brush size of 30 px, but you can vary the size if you want.
Select the colors from your reference image or use your imagination. I used my starting reference image and picked the darkest blue from the sky for the shadow parts, the lightest blue for the highlights and a light pastel color.
I could also have chosen a light purple color or a green tinted color, the sky is full of colors.

After you have brushed the colors use the smudge tool to blur the clouds.
Set the brush diameter to 30px.
Use very little pressure smudging the clouds, almost none.
And don't miss a spot, you don't want any of the hard pixels that the dry brush left behind.

Make a copy of your file and rename that file "yourfile"2.psd so you have a backup. Now you can safely flatten all the layers.
To make the image more realistic you can zoom in on the different parts and use the smudge and brush tools for details.
You can paint flowers, stones and trees into the scenery.
But for now we are going to finish the image using the "color dodge" and "multiply" modes with a standard brush setting.
Vary the brush diameter from very small to very large. Colors used are black for multiply and white for color dodge.
A tip is to duplicate the one layer you have so you can play around with the different tools and easily make changes undone.

Finished result: