Then create a new layer, either by hitting ctrl+shift+n or clicking Layer->Create New Layer.
With this new layer apply colors where you want them. Make sure to change the opacity of the layer so you can see where the color is going:
(click for larger image)
After you have filled in all the colors that you want, play with the modes to achieve the image you like best. I suggest using either overlay or multiply. Also, use multiple layers for different color for more flexibility.
How to change modes:
How to change modes: