Blender Render Texture Painting
I think you're missing one main point: a UV map is needed to make a correspondence between the mesh faces and a texture to paint to. And this UV is to be set up in the texture panel.

So the recipe is the following:


Have a mesh object
Go in edit mode Tab
Select vertices and unwrap (there is several ways to unwrap, I consider here the simple one): use U the "smart UV project" and validate





Create an image
Go to the texture panel
Choose the texture type as "image or movie"
Choose the image created above
Set the mapping to UV




Now you can paint:



Note that there are possibly several slots to paint to and you can add other textures or texture types from the "slot" tab available in paint mode:



In complement, here is how to create the image:


Open a new view
Set it to "UV/Image editor"
Use the "image" menu then "new image"
Validate the panel that opens, eventually renaming the image as you want