The Easy Stuff
Okay, most people know these things already, but it can't hurt to put them in the tutorial anyway. First of all, the Hue and Saturation controls are located in the Image menu and Adjustments submenu, and the keyboard shortcut to bring them up is ctrl+U. There are three sliders in this menu: Hue, Saturation, and Lightness.



To recolor an edit using Hue/Saturation with default settings, bring up the Hue/Saturation controls and adjust the sliders to your liking. It will change all the colors in whatever you have selected, or, if there is no selection, the entire layer. This method does not work on black, white, or any shade of gray, even if you up the Saturation slider. However, it is the easiest and quickest method. For this reason it is a good idea to make lots of layers on your avatar edits, so you can easily adjust the hue and saturation of one piece for customers without disturbing the rest of the edit. When using many layers, this method is also the most accurate and versatile.
Colorize
You may be wondering how to recolor a black, white, or gray image - for this, check the Colorize box at the lower right corner of the Hue/Saturation window. The entire layer will convert to different shades of whatever your current foreground color is (black, white, and gray make it shades of red). Adjusting the Hue slider with the Colorize box checked changes what color the entire layer is. This is the best way to add color to a black-and-white layer, and is also convenient for when a customer asks for a very specific color on an edit.
Before and After using Colorize


The Lightness and Saturation sliders are very useful with Colorize. The saturation will initially be fairly low, so most recolors will have you increase the saturation when using Colorize. Here is what a colorized edit looks like with the saturation increased:

The Lightness sliders will have less of an effect on saturation while using Colorize, since all shades of gray are converted to shades of whatever color you're using. Here are examples of what adjusting the Lightness slider can do:
Minus lightness and Plus lightness


The disadvantage to this method of recoloring is that it eradicates any variation in the Hue that may have already existed in an image. However, grayscale images don't have any hue variation in the first place, so it has no ill effect on them.
Selective Recoloring
If you asked me two days ago whether there was an easy way to accurately recolor a pattern that has multiple colors on one layer, I would have said you're out of luck, but when I was playing around I found a neat little tool. At the top of the Hue/Saturation window is a drop-down menu that is, by default, set to "Master." Leaving it at "Master" will cause any changes you make to apply to the entire selection, but using this menu, you can zero in on specific colors. Let's use this dress as an example again:

Now let's say a customer wants us to change the yellowy-creamy-color of the silk to pure white - in other words, they want that color desaturated. Using the "Master" menu, you can do that without disturbing the color of the roses or the trim on the dress. By changing the menu from "Master" to "Yellows" (because the color we want to change is yellowish), we can cause the changes to only apply to the yellow shades in the image.

Now that we've told the computer what color to change, we can change the yellowy white to pure white by dragging the Saturation slider all the way down.

As you can see, there is no longer a trace of yellow, and the roses remain untouched. By selecting different target colors in the menu, you could also change the red roses to yellow, or change the green leaves to black.
The downside to this method is that it only works on colors that have sharp transitions between themselves and other colors. A gradual transition from red to blue would not respond well to this method.
In any case, play with this method; you might get something good out of it.
And that's all!