Okay, for recoloring sprites, close GIMP and use MSPaint. I do it the old fashioned way (pixel by pixel) but there's a lot of shortcuts you can find on Youtube and such. For recoloring big ol' things like this there's a very helpful tool in the paintbrush called "color" in the mode dropdown menu that changes everything you paint over with it to a hue of a specific color.
For recoloring stuff like 3D game art, I suggest you use the wand tool in GIMP and either increase or decrease the threshold to your likes. Then you change the hue by selecting, "Colorize" to your selected areas. It's not perfect, but that's what I use.
First what are you recoloring? Sprites? Ignore Herr Shyguy's advice, because there is a quicker method for recoloring whole sprite sheets. In fact, you can recolor in a matter of seconds.
First, use the "Select by Color" tool (with the hand pointing at a color square or something like that).
Set the threshold to zero.
Click on any color you want.
Color all the selected pixels with the color you want.
Other pictures are a bit more complicated. Use the wand tool and adjust the Threshold. After that, use "Colorize" from the drop-down menu. This is Baby Luigi's advice.
But, I don't know what you mean by a "shaded effect". Tell me more in detail, perhaps?