All objects have prescense in three dimensions. Their form becomes powerfully defined under a light source. Planes facing towards the source are illuminated. Planes facing away are starved of light and remain dim. On a two-dimensional computer screen, it is the job of this shading to convey a sense of form and depth.

Now that we have shape from our lineart, and the foundations of colour, we can variate that colour to really bring our piece to life.

Establishing Light Sources

In order to begin shading an object, it is important to first establish where light falling upon it is coming from.
For outdoor settings, or indoor areas with consistent overhead lighting, it helps to pick a constant direction for light to fall from. Some people like their light to fall from the upper left corner of their image - I prefer the upper right and will use this for the rest of this tutorial.
This common kind of light all strikes your object at the same angle.

Areas with one or more lightsources illuminating shapes all around them are a special case and requires a little more work and attention. Good use of alternate light sources helps create mood and atmosphere in a scene. It is a rather obvious point, but important to note that in these cases, light noticeably decreases in intensity the further from the source you are.

The Shading

With our light source firmly established, we can finally shade our object, starting with the simple example of a sphere.
But first, an example of what not to do :

This called 'pillow shading', a great evil spoken of by pixel artists in hushed tones. It is the work of the devil, and appears to assume a single point light source hanging directly between us and our object.
Do not, under any circumstances, shade a shape this - it looks rubbish. This sort of radial tone gradient is suitable only for a surface lit by a very close light source - like the burning torches above.

As stated above, however, our light falls uniformly from the top-right corner of our image. Bearing this in mind, I like to start shading an area with two new tones - one darker than the base tone (lower RGB values) and one brighter (higher RGB values)
The lighter tone should be applied to surfaces facing towards the light source
The darker tone should be applied to surfaces facing away from the light source

Our sphere immediately gains form and depth. We can enhance this effect by adding even more tones, above and below our two new ones.

A this point you may find your object appears to light or too dark and need to correct the tones you are using. This is not uncommon.

These principles apply even more simply to a flat-sided shape.

A sphere is a rather boring and sterile object though. The same principles can be applying to a more interesting, less uniform object like this fat little creature :

Note how planes facing towards the light source are brightened, and those facing away dimmed. A good understanding of the three dimensional form of your piece is vital for shading, so that you can identify the amount of light these surfaces receive and shade appropriately.
In this example I have used a darker base colour and worked more toward the lighter end of the spectrum. The darker shadows are still there, but the overall effect is the lightening of the flesh to a tone I felt was more appropriate.

In some cases (faces, smooth machinery) detailed, careful shading is necessary. In others - don't worry about it too much. I find that messy shading often improves the texture of a surface.

As the flat-sided shape above showed, the distance between different shades is by no means constant.
For more cuboid shapes, the top and bottom surfaces are best implied by a narrow area of shading. Observe the example of this slab of rock.

Note again that on natural surfaces like this, rough shading can help.
Varying the colour as well as the brightness of new shades can also produce some interesting results ( increasing or decreasing one or more of the RGB values more than the others ). You will need to do this for non-white lighting as well.