Ok, here's what you want to do:
First, if using a Polygon object, map its UV's, otherwise, your painting will overlap the UV's and it'll look mighty ugly.
Second, give your object a new material, so that it's not using Lambert1, which is the default for all objects you create. If you don't, then everything you make will have your painting all over it.
Third, you want to make sure you've set your project folder, so that it will save your texture in a place you can find it. File > Project > New to create a new project directory, and if you have one: File > Project > Set to choose your project directory to keep track of stuff. With your project set, your texture will be saved into the 3DPaintTextures folder in your directory.
Ok, so once you've got that:
1. Select your object.
2. Go to the Rendering menues, Texturing > 3D Paint Tool > Options.
3. In the options, scroll down and choose which Attribute you want to paint (probably "color" which is default, I believe) and what format you want your texture to be (I'd choose Targa, but that's just my opinion.).
4. Below the Format choise, click "Assign Textures."
5. A dialog window will open asking you to choose a size resoution. I normally use 512x512. You can do what you want, but it's normally a good idea to keep your textures square.
6. Once you press the "Assign Textures" button in this box, your object may shift to a lighter gray color. Scroll back up in the options and choose your color, choose your brush Radius, and get to painting!
7. This is important: when you're done, click the "Save Textures" button under the "Assign Textures" button.
And there ya go!