There are two options for painting. You can either use the Sculpting Paint Brush and colour the surface by vertex colours, or you can use the Texture Paint Brush and paint onto a 2D texture that is wrapped around your model.
Vertex Colour painting is handy as you don't need to setup UV coordinates on the surface. Texture Painting - or loading a ready made texture onto a model - is a good way to add quick fine details without needing a high resolution mesh, although for complex models you may need to use the Texture/UV mapping tools to setup UVs before painting.
VERTEX PAINT
TEXTURE PAINT