OrganicDye

Natural materials have been used to color objects for 40-170 thousand years (that we have evidence for).
The observed ancient pigments:

Iron based natural colors
Formula Fe₂O₃ - three oxygen atoms bound to two iron atoms, AKA ferric oxide.
In this formula it can crystallize into Hematite, grey to black in color, and commonly found in rocks and clay; when weathered it can become Maghemite, as a brown to yellow color often found in sediment layers; or grayish blue or even white.
When hydrated (Fe₂O₃*H₂O) it can form complex minerals of varying color.

• Red Ochre is hydrated ferric oxide and has additional Hematite.
• Yellow Ochre is hydrated ferric oxide.
• Hematite is dehydrated ferric oxide.
  

Manganese based natural colors

• Manganese Oxide II MnO forms green crystals or powder
• Manganese Oxide II/III Mn₃O₄ can be brownish black
• Manganese Oxide III Mn₂O₃ brown or black crystals or powder
  

Carbon based natural color

• Charcoal Black - unfortunately can cause cancer in specific forms (soot, charred food).
  

We know about these because they have survived for tens of thousands of years in caves and sheltered areas. The gold standard for archival. Other colorants are less permanent, but still useful on a human time scale.

I'm specifically going to call out tannins and berries here.