There are many different methods to coloring an image, so let me take you through them!

Keep in mind that the original color scheme as well as the brightness and contrast of an image will determine the effect any of these methods have. Some colors may not work well on a certain image. As always, experimentation is the only way to find what will and will not work.

Here's the base we'll be working with:

Hue/Saturation

By pressing CTRL + U or by going to Image > Adjustments > Hue/Saturation, you can change the color in two ways.

First, make sure the Colorize box is unchecked. By sliding the Hue scale back and forth, you can tweak the color of the entire image. This is a fine way to make slight changes, such as making an image less red. But you'll find that if you stray too far from the original color, your image will look strange and grainy. If you're looking for a surreal look, though, this will be useful to you.

A good example, at Hue +20:

A bad example, at Hue +150:

The other upside to Hue/Saturation is, obviously, being able to alter the saturation. This makes the color of an image more or less intense. If you have an extremely intense image, this will come in handy to tone down the overwhelming color.

More intense, at Saturation +50:

Less intense, at Saturation -50:

Now, click the colorize box, and you're able to change your image to a monotone color scheme. You can get a muted effect with low saturation, or a brightly colored effect with high saturation.

Hue 30, Saturation 25:

Hue 200, Saturation 40:

Color Balance

By clicking CTRL + B or going to Image > Adjustments > Color Balance, you can change the - surprise - color balance! This is a very helpful tool if an image has way too much of one color and you need to tone it down. Here, I've first amped up the red in my base using Hue/Saturation, so I can show you how to tone it down with Color Balance.

Midtones: -60, +25, +20

You can also use Color Balance to simply change the overall color scheme of your image. The possibilities are endless with so many different values of color in the midtones, shadows, and highlights. Here are a few examples of what you can get.

Midtones: -75, -25, 0
Highlights: 0, 0, -60

Midtones: +85, +50, -45
Shadows: 0, +40, 0

Midtones: +40, 0, +50
Shadows: +45, 0, 0
Highlights: 0, 0, -80

Variations

I use Variations on almost all of my icons, because it's so simple and can do so much for an image. Go to Image > Adjustments > Variations to adjust the color, brightness, and saturation step-by-step. You can add a small tinge of yellow, or flood it with blue, or mix red and green for a neutral look. Whatever your heart desires!

Again, the possibilities are endless, but here are a few examples, all with the slider one notch to the left of the center and on Midtones.

More green x2, more yellow, more red, darker:

More yellow x4, more red x2, lighter x2:

More cyan x2, more blue, lighter, less saturation x2:

Using Layers

Layers are another great way to give color to an image, and you can get effects with layers that you can't with the other methods.

One way, which is basically the same idea as using Colorize with Hue/Saturation, is to fill a layer and set the style to color. This will make the image completely monotone.

Using #C87D82:

By setting the layer style to hue, you'll get an entirely different effect, depending on the color and intensity of your image. With a less saturated image, you'll get a softer color; but with a brighter, more intense image, you'll see a brighter, more intense color.
Using the same color as above, here are two examples. The first is with the original base, and the second is with the yellow and green cranked up with Variations.

Using #C87D82:

Using other layer styles, you can get many different effects, most of which will maintain a trace of the image's original color scheme. You should use a light color with the styles that will darken an image, such as multiply, hard light, and vivid light. Consequently, use a dark color with the styles that will lighten an image, such as lighten, screen, and color dodge.

Using #FFD300 on multiply:

Using #742D5F on screen:

Using #6E941F on vivid light:

Using #384257 on color dodge:

For a duotone look, a gradient comes in mighty handy! Here is one example, but for more information on gradients, check out the gradient tutorial.

Using #A44B4B and #7A7F22 on hard light:

The exclusion layer will give you a very interesting muted duotone effect, if you use the right color. Here is one example, but for more information on the exclusion layer, check out the exclusion tutorial.

Using #002A5F on exclusion:

That's about all I can tell you about color! Remember - experiment, experiment, experiment!