YanSculpts is doing a basic unwrap of the model in your link.
From MarkG's answer:
1. Create clothes for a model. You can lay a mesh out on your model, and have it "cling" to the form[...]
2. Create a better arranged mesh to sculpt on [... Subdivision] creates VERY dense meshes. A better approach would be to retopolize your mesh before scultping so the edge flow of your polygons worked with you, instead of against you. [...]
3. Lower the density of your mesh so you can animate it.
Retopology is simply creating a similiar shape with different topology. (Usually by snapping new vertices onto existing high density faces.)

To paint your model, you have two basic options:
Texture Painting
A UV texture is a picture (image, sequence or movie) that is used to color the surface of a mesh. The UV texture is mapped to the mesh through one or more UV maps.
- PRO works with low and varying density of vertices; this means highly detailed paint jobs on low vertex counts are possible
- PRO export: colors are on a 2d image, which can be edited in image editing applications (Photoshop, Krita, Gimp)
- CON we need to uv unwrap the image onto a 2d surface beforehand
- CON with complex distorsion, can be slow on parts of the model
Vertex Painting
Vertex Painting is a simple way of painting color onto an object, by directly manipulating the color of vertices, rather than textures [...]
- PRO no need to unwrap the mesh, can start painting immediately
- CON some angles and occlusions will leave lone vertices unpainted (in Blender) unless you rotate/zoom/readjust the view
- CON needs a high vertex count, since color data is applied only per single vertex and interpolated in between them
With both methods, you can not go back to dynamic topology (changing the vertex count), otherwise your uv or vertex color data will be reset. In both cases you may edit the mesh in Edit Mode preserving the existing data.
The manual explains both processes, well. I would recommend texture painting. Although texture painting is usually not done with very dense models, its only drawback is speed (as Blender isn't designed to unwrap high density models).
If you can easily go into edit mode, navigate and unwrap by pressing U > Unwrap, without Blender constantly freezing, then proceed to unwrap.
If your model is to dense you can try to decimate it with the decimate modifier, which is an automated form of retopology as well and provides very bad topology. But as long as it doesn't cause visual artefacts, bad topology shouldn't concern you, since your aren't planning on animating the geometry.
Most dynatopo topology can be decimated quite a bit with little visual difference.

From Craig's answer:
as far as I know, there is no way to 'texture paint' without having UV mapping on a new lower poly mesh.
The basic UV unwrapping process can be done with a high density mesh. (It just can get very slow computationally.)
- Select your model, go into edit mode, select all vertices and press U and choose unwrap.

This will probably be slow and produce a horrible result. YanSculpts model has 23,000 vertices and he solves the unwrap by only unwrapping small parts at a time. To do this, box/circle select some vertices, then press U to unwrap. You can immediately position them in the 2d UV layout (UV map).

L for island selection. G, R, S and many other hotkeys work as in the 3d view.
Read up on other unwrapping methods.
- Once unwrapped you can load an image texture or create a new image texture and save it.
Setting the 3d viewport to textured viewport shading will display the active texture (with Blender Internal).
- Now you can edit texture paint mode, set the image as the source and start painting on it.

With vertex paint the unwrapping process is skipped.