I agree with Mediaevumed that this is an anthropology question for /r/AskAnthropology, I would add that you could also ask /r/Archaeology. Being an archaeologist (I hang out here in /r/AskHistorians for these questions), I'm going to take a stab at an answer.

I'm going to assume that by "cavemen" you mean any prehistoric human populations. I'm going to further assume that you are asking about rock art. Rock art is found all over the world, there are famous places like Lascaux in France, the Chumash Painted Cave in California, and Burrunggui in Australia. These are just the painted variety, there are other varieties of incised or ground rock art, such as the petroglyphs in the British Isles. You asked about paint, so I will talk about the paint.

Painted rock art is most commonly found in three main colors: white, black and red. These paints are produced using a natural pigment and some kind of oil. Red paint, for example, can be made using ochre (iron oxide- naturally occurring in rock) for pigment and animal fat as the oil. These materials were then painted onto the rock using a brush or fingers.

You've strayed well into the realm of what we call pre-history, i.e. stuff that predates history. In this case, by a whole whole lot.

I'd encourage you to head over to /r/askanthropology or /r/anthropology and see if any of the fine folks there can help you out.