I have multiple videos about texture painting in Cycles:
This 16 minute video is the shortest because I use automatic UV unwrapping and because I use ONLY texture paint whereas in the other videos I use a combination of texture painting and face-by-face coloring (multiple slots and multiple materials). But I think you will still find this video to be quite complete for it shows how to use face masking while you paint, how to paint symmetrically without using a mirror modifier, how to vary the thickness and sharpness of painted lines, how to improve the lighting, move the camera etc and above all how to pack or save your UV image so that it is not lost when you save your BLEND file and close Blender.
This video is 24 minutes longer, a bit longer than the one above, because but it also shows that texture painting can be combined with face-by-face coloring (adding slots and additional materials). It uses the same automatic unwrap that is used in the first video.
Finally, this Vimeo video is shorter in the sense that it is 14 minutes, but some parts are speeded up. Like the previous one, it shows a combination of face-by-face coloring and texture painting with a brush. It shows the head being given seams manually before being unwrapped, which is advisable if you want to paint directly on the unwrapped UV image.
If all you want to do is apply a solid colour to your 3D object or to certain faces of your 3D object then see the 'materials' page, not this one. If you want to be able to have more freedom in your painting, then 3D painting is a good option - it lets you paint as if you were using a paintbrush or airbrush.
There are two ways to paint your 3D object. In both cases you will first need to 'unwrap' the surface of the object, a process which can be compared to removing and flattening the peel of an orange. Inevitably, tears or 'seams' will appear as the object is unwrapped - these seams can either be placed automatically or manually. Placing the seams manually allows for the unwrapped image to be in fewer parts, which is important if you want to paint directly on the unwrapped UV (flat) image. This is problematic though when you paint on the edges of the shapes (called islands) in the UV image, which correspond to the seams. It's usually better to paint directly in the 3D viewport since it is more natural and since it avoids problems of painting across seams.
It's also possible to paint the UV image in a separate program such as the GIMP or Photoshop, but that approach is not discussed here.
IMPORTANT: when you do UV unwrap you create a 2D (flat) image that won't necessarily be saved when you save your Blend file so there is a risk that you may lose the image. There are two ways of making sure you don't lose your image. Whichever method you use, you should use it after you have finished modifying the image since otherwise you will lose later modifications to the image. An asterisk next to the header of the 'Image menu in the UV / image editor means the image has unsaved changes.