(And...I'm going to give my best trying to explain the best I can, I'm sorry Miruki, this is for you!)
So...Where to start? I don't even know!
This is my method, do not take this as an absolute truth(Becase it isn't there will never be)
You can catch whatever you find useful of this and use it .
What to do first?
Open your prefered program(I use Photoshop cs3) and input the size of your canvas(Be sure to
work on a bigger canvas than the final product, at least the double of size. For example if your canvas is going to be
1366 x 768, work it at least on 2732 x 1536, then when you finnish it, resize it to it's original size )
Now that we have or canvas, let's think about what are we going to do, and get a bunch of references ready(I usually
don't do this...orz But you totally should! )
For this example I'm going to paint a dusk landscape, something like this one
Examine which colors are the predominant on the picture, cold colors right?(blues, purples..etc) but also got warms(not as much as the colder ones)
Start with your canvas, and paint it with the predominant color of your bg(Why? We want to make sure this color affects the whole setting)
Now, let's sketch our background.(This is where you apply all your knowledge about drawing, perspective and proportions...I know this very vague so I won't corrupt your head with filthy lies)
I tend to do everything in one layer(You can work faster on that way buy it's hell if you want to edit haha, If I want to edit what I do is paint over everything...But probably that's the worst way to work a bg)But this time I'm using layers. See? Create one layer and start sketching. Use your favorite brush there...I use that one marked on the screencap to sketch because it's sharp.
Other more polished artist(I suggest using this instead of my "me avoiding lineart") after sketching, they go for a cleaner sketch or much better a lineart. Choose which one will favor your final result.
Before I start coloring I have pictured in my head which parts of the background are near and which ones are farther. The nearest ones will have a more sharp coloring and the elements which are farther will be more blurry. It helps a lot thinking of your bg as a layered picture(like the one bellow, 3 parts)
Also remember that farther elements will have a washed out color.(Specially on daylight)