En primer lugar debes asegurarte en Imagen -> Modo, que estás en modo RGB o algún otro modo de color que no sea Escala de Grises.
Luego sigue estos pasos:
1. Crea una capa nueva encima de la capa de la foto.
2. Cambia el modo de la capa a Color. Se cambia en la paleta de capas, junto a la opacidad. Por defecto pone Normal.
3. Échale paciencia, elige el pincel de grosor adecuado para cada zona de la foto, elige el color y pinta. Siempre sobre la capa de color, cuya misión es preservar la luminosidad de lo que haya debajo. Por tanto, conservará los tonos oscuros y los claros de las capas inferiores. También puedes realizar selecciones y rellenarlas con el cubo de pintura o con la opción rellenar del menú, pero siempre sobre la capa de color.
4. Imagen -> Acoplar una vez terminada.
5. Archivo -> Guardar como. Elige un nombre distinto para no perder la imagen original. Guarda el PSD, también, con las dos capas, pues es bastante normal hacer retoques más adelante.