There are a lot of shortcut ways that are not perfect but can be good enough. There is only one truly perfect way to do it, though, and it is a real pain in the butt. And that is to make a selection of the garment (or whatever you want to change) VERY carefully, and then use the hue/saturation tool, command or cntrl-U, to change color. The key is in making a top-notch selection. I highly recommending going into the quick-mask mode (on the bottom of your tool palette, check your manual and you'll find it) to use the paintbrush tool to very carefully paint your selection, using the right size brush to precisely get every pixel you want and none you don't. Of course it helps if you're a skilled draftsman, which I am not. But with time and patience it can be done.
This is the ONLY way to make this sort of edit truly seamless and artifact-free. And the good thing about the hue/saturation tool is that it will leave your brightness values intact if you wish, thus preserving the shadows and highlights and such, thus keeping the effect seamless. No one need know anything was changed but you.