I am going to start by saying this tutorial Is probably much easier than you expected and is well worth the try.

First we want to start by opening our project/picture that we want to apply this affect to.
I have chosen to use this picture:

Select the Magic Wand Tool (), we're going to use this to make selections.
The selections are going to be the colours that we are going to transform.
Using the Magic Wand Tool simply click the selections, you wish.
If there are more selections that you wish to change or that weren't picked up in the first/original selection or to add the same colour at the same time simply hold shift or select and continue to select other places as shown in the pictures below:

When your satisfied that you have managed to catch all the sections of your picture you wish to re-colour simply press the keys Control+U, this will bring up the Hue/Saturation tool, we now want to select the Colorize box.
We can now adjust the selections to whatever we wish, when your satisfied press ok.
I used the colours:
Hue: -65
Saturations: -10
Brightness: -5
I was left with:
Heres what happened to my image:


(You may want to write your settings down somewhere as it helps to keep colours the same if in the next step you find some unchanged colours)

If unsatisfied you haven't changed all colours simply run over your picture (Maybe magnified) and look carefully for unchanged colours.
Repeat this step until satisfied.

WE'RE FINISHED!

This what I'm left with:

Don't forget to experiment.