Let me show you how easy it really is.
- Open your black and white photo and copy it to a new layer
- Under Image > Mode > change it to RGB if it isn't already
- Select your foreground color then select a soft edged brush
- In the options palette for the brush change Mode to Color
- Change the opacity of the brush down from 100% (try 70-80% to start)
- Start painting in color - adjust the size of the brush as needed
- If you overpaint into an area you didn't want, just use the sponge tool set to desaturate to remove the extra color