Okay, I'll be using my illustration of The Boss from Metal Gear Solid 3: Snake Eater for this tutorial. Mostly I'd like to cover the nuances of using photoshop for colouring (or "coloring" for you crazies south of the Canadian border) line art. I can only assume that if you want to colour line art, that you have line art to begin with so open photoshop and lets giddyup.
the boss metal gear solid 3 snake eater
First off - image resolution. Decide first what you want to do with your picture when complete. An image that is only going to be displayed on the internet needs far less resolution than one that is going to be printed out, and working at a lower resolution to reflect that can save you a lot of headaches working on details that won't even appear in the final work. In general I print my artworks at a final size of 11" x 17" and like to stay over 250 pixels/inch. For this picture however I went with 400 pixels/inch since my computer can handle it, which results in a dimension of 4400 x 6800 pixels. Also keep in mind that even if you computer seems super speedy working on a file that size in black & white with only one layer, once you add layer after layer of colour you will be in "I'm going to kill myself because this is so slow" territory. Trust me - I've killed myself a few times already.
image resolution
Okey dokey. We must first consider what kind of line-art you have. Is it smushed irrevocably to a layer of white or is it floating free on its own layer? Are you kicking yourself for not putting it on it's own layer? Well you shouldn't be because it makes no difference (or very little).

Either way I'm going to get you to create a layer of background white (ctrl+shift+N, select all, fill with white) which we aren't going to touch. It will merely act as a placeholder so we don't have those dumb checkerboards showing through. Now take your line art and set it on top with it's "Layer Mode" set to "Multiply". From here on out your line work will remain on top and all subsequent layers get sandwiched between the white and the lines. It's so simple that you probably just shat yourself.
first two layers
When are we going to get to colour, you ask? NEVER HAHAHA!..... I mean, ahem... not yet.

First we must decide how many major areas of colour there are. This is going to determine how many layers we need. Is your drawing of a bald naked person? Then you will need very few layers - one for skin and one for background. Is your drawing of a collage of intricate costume wearing Cirque De Soleil performers? Then you can expect to have a lot of layers for each distinct area of colour

In my case there are some obvious distinctions - the main uniform jacket and pants, the straps and gloves, the hair, and the skin.

I add new layers for all these areas and name them accordingly. Names are very important when you start making a lot of layers, photoshop even lets you assign different colour schemes to your layer palette to differentiate things.

Set all your layers to 'multiply'. Or don't. But just in case you forgot to put your line art on top this will let the lines show through.
other layers
Now we grab the old paint bucket tool, which I despise by the way. Start with whatever colour you want to block in first. Pick a colour somewhere in the middle of where you want the darkness/lightness to be and start filling in the closed in shapes making sure that your paint bucket is set to "all layers".

The reason I hate the paint bucket tool is that won't always fill cleanly inside all linearts. If there is any area of greyish in your linework then the paint bucket usually won't fill it and instead leaves an ugly-as-rotting-fruit blotchy area. I set the tolerance as low as I can without the paint spilling over the lines and also I like to click twice when filling so that it fills in a little more completely.

Things don't need to be perfect just yet.
paint bucket
The next step is grabbing your brush with it's opacity set to 100% and fixing all your edges or wonky areas. Simply go around and colour in any spots that were missed and use the eraser tool to clean up overspill. This step generally involves some heavy zooming in.

For ease of use I like the keyboard shortcuts "b" for the brush and "e" for the eraser, as well as " [ " and " ] " for increasing and decreasing brush size.  Which is tonnes faster than using the brushes palette.

For extra speed use "shift+[" and "shift+]"  for tuning up and down the hardness of your brush edge.
fix me
So, have you blocked in your first layer? Did you already go on to the other layers without waiting to hear about my super secret speed tip? I hope not, because this will save you a lot of time.

In you layers palette do you see the little thumbnail image of your recently brushed in layer? Well hold 'Control' and click on that thumbnail. The dancing ants have come to congratulate you on selecting your layer!

Now you need only press "Control+Shift+I" to select inverse and voila! You can now proceed to your next layer/area of colour without having to worry about overlapping anywhere you painted in your previous step.

If you get sick of the dancing ants simply press "Control+H" to hide or unhide them.

The more layers you block in the more you can add to your un-selection. Simply select the first layer with 'Control' click and then subsequent layers with 'Control+Shift' click. And then again invert your selection and move on.
bad boys
As you reach the end of blocking in your colours you may find you have little bits of things that need their own separate layer but don't seem to warrant a whole layer to themselves. I usually amalgamate all these items onto a "misc." layer.

Once you are done we are ready to turn the power of computer awesomeness into something so wicked you teem with respect for Charles Babbage.

Select each of your layers and hit the little checkerboard in turn to 'lock' the transparency! That's it - all your kindergarten training of colouring inside the lines was just made obsolete! You can now draw on each of your layers and you will never spill outside of the areas you have already blocked in.
transparency lock
This is the point where I have to piss off anyone who doesn't have a tablet. I just have bad news for those of you who can only use a mouse - the colouring gets a lot harder from here on out. Mind you, not impossible, I myself started out only using a mouse for quite some time.

Mouse users will simply have to spend more time making use of the "Flow" setting for their brushes.

Tablet users need only go to the brushes palette under "Other Dynamics" and set the opacity and flow controls to "pen pressure".

I imagine anyone reading this at least has a hobbyist's interest in digital colouring and I highly recommend investing in a tablet to help you enjoy this wonderful process even more.
brush settings
Now, choose whichever layer you want to start shading first. I usually start with the one with the largest area in order to help firmly establish lighting tone and direction.

If you are colouring your own work than you probably have an idea of the lighting you want already. If you are colouring someone else's work then perhaps they had an inkling as to the lighting when they started drawing and have included some shadows in the linework which you can use to guide you in your shading.

There are several ways to approach the initial shading. I start with my medium tone and then pick a lighter and a darker shade to switch between. Avoid using white and black, sure they do the job, but they do the job like a dog trying to mow the lawn - it will be bad and probably involve a lot of blood and exorbitant veterinary bills.

As a general rule I make shadows less saturated and highlights more saturated. Use your own judgment. If it looks good - do it. In this kind of work looking good is all that matters.
soft shading
You can also choose between a soft edge brush or a hard brush. A lot of artists I know prefer to use a hard brush and start by blocking in large areas of colour and shade first with little care for the small or smooth details at this stage.

The advantages of this method are clear - it takes much less time and gives a much more defined shape to everything, all of which can be refined later.

You may even want to reduce the resolution of your image and do a couple digital thumbnails quickly to find a good lighting scheme. Working in black & white at that stage can also help. Even when I start in full colour I almost always change the initial shading colours by the time I am finished.
hard shading
Okay, so now that the dog has mown the lawn you should have something that looks pretty well shaded. Go in and shade small details to taste. I also usually break my own rule at this point and grab some white and throw in some highlights only on the shiniest objects. Too much shine and it will look like everything is made of wet leather. Use a hard round brush for sharp highlights.

Also at this point if you feel like some of your shading is too hard and you want smoother transitions simply grab the 'smudge' tool and go at 'er with a soft touch. I just wiggle the tool around on top of areas I want to smooth. Stay away from the 'blur' tool since photoshop's idea of 'blur' at '100%' is more around the lines of, "I don't want to blur anything unless you are prepared to wait a million years for this goddamn tool to do anything close to what you would call blurring".
smoothing

Now take a break to pet the nearest bunny or kitty.

The dog doesn't get pets until it finishes skimming the pool.

When you are ready Go On to Part 2

An In Depth Look at Digital Colouring