And when should I use each?
With Vertex Paint, you’re assigning a color to a specific vertex (or set of vertices). Texture paint allows you to arbitrarily paint on your mesh, regardless of topology (you should UV unwrap your mesh prior to texture painting). A workflow I like to use is to block in my basic colors using Vertex Paint, unwrap my mesh, bake those colors to a texture, and then use Texture paint to put in detail.
Take a look at this tutorial on blender cookie