Start out with prepared line art...
At this point I would assume you have already taken the basic steps outlined in the "Basic Sketching/Line Art" tutorial so that you have your line art in one layer and then a separate background layer behind it (you will be creating layers between these to color in). There are many "styles" of coloring, but for most of them you will want to start out with your basic colors blocked in (as in the example shown at the left).
Choosing your colors
Choosing the "right" colors for an image can be hard - there are so many factors to consider. First of all you may be coloring an 
image of a well known character (or one of your own characters) and they wear standard colors/costume. Keep in mind that, for example, just because Superman wears blue and red it doesn't always have to be the SAME blue and red. If Superman is outside on a cloudy day his outfit probably won't appear as bright as if he were standing in the sun... AND lights can also have color to them - the sun is more yellow then the moon! Someone underwater might have more blue/cool colors in their clothing then someone wandering around the sands and pyramids. Beyond that there is also the mood which you, as the colorist, want to show with the picture - is it happy, exciting, sad, angry? Colors have different meanings and color combinations have different effects. You may have heard the term "Color Wheel" used - this is part of "Color Theory" and can be very useful in selecting colors. If color combinations is of particular interest (or trouble!) to you I suggest reading a book on Color Theory as it may help you a lot. Generally speaking in my artwork I prefer to choose colors that are not too bright. For the example in this tutorial I am using the palette of blues, reds, purples, and browns shown here - most of these are fairly "muted" having a good deal of black or white (or both) in the color so that it is not too bright/intense.
Blocking in the basic color
You will want to be coloring UNDER the line drawing (or "ink") layer - creating new color layers between it and the background layer. As in the example shown here I suggest filling your background something other then white. White can be distracting so (unless you plan to have the finished background white) fill the background with a fairly neutral color (in this case I made mine a muted green). Do not worry too much about the background color or the colors that you block in being exactly right, you can always adjust them later.
I use a separate layer for each color as shown in the example image above (not for each area, but for all areas of one color) - this allows me to change or adjust the colors individually if I need to and makes shading a lot easier later. At this point just color each area in solid. There are two ways to go about this: You can use a brush and carefully color each area or you can use the marquee (selection) tool to select an area of your line art and then switch back to your coloring layer and use the fill too. If you use the second method I would suggest "expanding" the selection before you fill it so you are filling a little under your lines. Even if you use this "selection and fill" method you will probably still need to use a small brush to color some of the smaller areas
Once you have your basic colors blocked in, each on a separate layer, turn on the "Lock Transparent Pixels" setting for each of the color layers. This will prevent you from coloring outside the areas you have blocked in while you are shading etc.
