A material defines basic properties to be applied to the entire surface of an object. A texture is used to add variety to the material.
For example a material defines a simple blue colour for the cube. The same colour is used over the entire surface, with variation due to lighting.
Adding a texture can then add some variety to the colour. In this example I use a cloud texture to add some green patches to the cube.
Textures can be used to alter almost any part of the material properties from diffuse and specular to transparency or normals (that provides the appearance of surface detail without the complex geometry). A single image texture can also be used to define the surface colour of the entire model.
The above example uses blender internal but the same applies to cycles, it is just less separated in cycles, with texture nodes being mixed in with simple diffuse nodes.
Where vertex painting assigns a colour to a single vertex that can be used to colour the model around that vertex, texture painting is used to paint onto an image of any resolution you choose, allowing you to specify much more detail to your texture.