Basically there are two methods for painting textures; projection painting and polypainting.
Projection painting requires that you have a model with UVs assigned, a texture map selected under Tool > Texture Map and the Projection Master plugin to paint the texture (shortcut ‘G’).
Using the Projection Master plugin is described >> here << but the general workflow goes like this: Rotate model, activate plugin to ‘drop’ model, paint colors/deformation, activate plugin to ‘pickup’ model. Repeat.
Polypainting, like regular sculpting, relies on high polycounts to get fine details and even polygon distribution can be important if you are not able to subdivide enough times (although in 3.5R3 you can polypaint HD geometry). If you assign UVs to your model you can convert the polypaint into a texture map (Tool > Texture map > New From Polypaint).
To start polypainting simply enable Tool > Polypaint > Colorize or press Color > Fill Object which also enables Colorize.
Color > Fill Object has no effect on the assigned texture. What it does is fill the currently visible and unmasked polygons with the currently selected color and/or material (depending on the M / RGB / MRGB switches in the Draw palette).
I would strongly recommend polypainting for creating your textures. Apart from the added controls and flexibility afforded by using the regular brushes for painting, the workflow is much nicer. UVs can be updated at any time without destroying your texture (simply create a new texture from polypaint), Brush > Auto Masking offer many texturing possibilities ( polypainting by cavity depth is plain awesome), in 3.5R3 the Brush > Alpha and Texture > Polypaint Mode allows standard, colorize, multiply, lighten and darken painting.
As for Projection Master I cannot think of many benefits anymore. The workflow always tested my patience but with 3.5R3 the draw state is no longer remembered between drops and pickups which just adds to the frustration.
Hmm, that turned out longer than I intended 