There's one of two ways that I made backgrounds on King's Quest III Redux. One method involves coloring a scanned sketch, and the other involves pixel editing pre-existing backgrounds. I've used Photoshop 7 and above for all of my work.
To pixel-edit backgrounds, I copy the original background layer of the image, and paste it as my top layer to track my progress. This layer can be switched on and off to see all of the improvements that have been made along the way. When encountering a large number of scenes that require a similar color scheme; for example, forest scenes, I create a new image just to make a color palette I can go to when needed. It's good to plan out your colors for each element in a scene, such as neutral colors, as well as light and shadow colors, for rocks, trees, etc.
Following basic principles that closer objects will be in sharper focus, plan on detailing more as you reach the foreground. Since the King's Quest remakes have a resolution of 320x200, I've primarily used a 1 pixel brush for detailing. When you want to define objects, while leaving a soft, anti-aliased edge, use the paint brush or airbrush tool. For detailing treebark, jagged edges on rocks, the edges of wooden planks, etc, I use the pencil tool on a very low opacity, no higher than 20%, to add definition without giving the image an over-pixelated appearance, and more in favor of a hand-painted scan like the Sierra classics.
To color an original image, it's important to have a detailed drawing with clean lines, free of smudges, before scanning. I recommend 11x14 paper, and having a flatbed scanner large enough to fit these dimensions. Once the image is scanned, load it in photoshop. On the top of the toolbar, under "Image", select rotate canvas to place the image in its proper position. Once this is done, go to "Image" again, and select "adjustments". A pop-up window will appear. Select the "levels" tool; there will be three sliders for highlights, midtones and shadows. Play around with the contrast so that the black lines are more defined, and the white empty spaces are cleaned up. The better your scan, the less adjustments are required. After adjustments go to "Image", then "mode", and select grayscale. Resize the image to the resolution you will work with.
To begin coloring, create a new canvas matching the dimensions of your sketch, and select RGB color as the image format. Make your background color a neutral gray. It will make it easier on the eyes, and easier to see the colors when doing the underpainting. Once your new canvas is opened, select and copy the resized sketch, and paste it as your top layer on the new canvas. On the layer toolbar, you'll see a window that currently says "normal". Click on the window, and change it to "multiply". The white empty space will become transparent, revealing the background layers beneath the sketch lines. From this point you can build up layers beneath the sketch, starting from the background, turning off the sketch layer, or lowering the layer opacity to suit your needs when coloring.
Have fun and keep practicing!
Each background screen starts as a painstakingly detailed piece of concept art. Once approved, the artwork is scanned and digitized - ready for color.