Hi Ean,
We typically use a graphics software package such as Adobe Photoshop or The Gimp. They can all achieve the same result, it's more a matter of preference.
Much of the time it's a matter of sketching the background first (either with pencil, or directly on computer with a tablet), laying out the various elements, in order to achieve a composition which works. I know when I was working on ATOTK, I wasn't very good at composition, but you get better with practice. It also helps to look at references, go out in nature and draw what you see (not what you think you see).
Composition is very important as it makes or breaks a scene. Often it can take several sketches before you come up with something you like. Getting feedback from other people is also important as it helps you to learn where to improve.
After the sketching, it's a matter of choosing colours (depends on your light source and intensity), blocking the colours in, and adjusting them so that it is consistent with the lighting. Understanding form is important in order to achieve realistic 'shading'.
After that, and only that, should it be a matter of details and refining it down - often people get bogged down in the details first before considering composition and colour.
Regarding media - if you understand form and colour, the medium you use is irrelevent, and you should be able to achieve decent results with traditional media. The only difference is that you would want to have a good quality scanner, and you'd probably need to do some digital editing to tidy it up.
So I'm afraid there's no real quick tricks - it mainly comes down to practice, practice and more practice, and continually trying to improve. But if you have patience and enjoy it, it's definitely rewarding in the end.
Loomis books are a good start to understanding the basics:
http://www.alexhays.com/loomis/
