Chew sticks have been found archaeologically since ~3000BC. I was shown a specific tree used commonly in Africa, likely for millenia, for oral hygiene.
Examination of Egyptian mummified remains show only 10% with caries, 20% periodontal disease and 50% of all teeth with dental calculus.
No evidence of dental treatment was found. Tooth erosion was prevalent, likely from chewing grains milled by stone.
Dental decay was rare in ancient Egypt but more common among aristocratic families found in the more recent Giza pyramids. This suggests that increased carbohydrate consumption was a cause.
One of the earliest discoveries of dental work was found in Sidon, Lebanon. 4 teeth wired together with gold wire from 4-500BC.
By the 1st/2nd century, Romans were treating toothache by drilling into the tooth and placing fillings and herbalist medications. They were also removing tartar with tools, having identified calculus as a cause of dental disease.
Not a Historian - but am a Biochemist
Certainly, much of what we consume now didn't exist/wasn't commonplace (mcdonalds, starbucks, sugary cereals) years ago, basically anything that bacteria can metabolise, or that breaks down enamel will cause decay
-Simple (faster to be metabolised) sugars, Starch (crisps are the worst thing to eat before bed), Fats, Acid - coffee, fruit juice, cola etc.
All of which constitute a large percent of our daily calorific intake.
the distribution of dental caries in patients over 35 years can be super-imposed to that of the countries where the food industry has developed, with, in particular the addition of sugar in the food diet. Thus, countries with a very high incidence are Western Europe, North America, Australia, Brazil, Chile and Peru. However, in Africa, South and East Asia the incidence is much lower [1]. This will tend to also self correct as preventive measures against dental caries have been taken in children.*
EDIT:
This isn't really true. In the upper paleolithic, humans that made it to age 15 were expected to live to an average of 54 years of age - source. The data is confused because of a high infant mortality rate.
As for bacteria;
From the nineteenth century, a very sharp decline in the biodiversity of dental bacteria has been observed as well as the onset of the oral microbiota associated with the presence of caries with a predominance of S. mutans.
So yes, more decaying bacteria, it's just our fault from diet.
This is something done up by a Canadian cultural historian. The short version is people've groomed and cleaned as long as we've been here (we have records going back to Egypt), the brush started in medieval China, the American versions were patented and went into production in the 19th century, but it only caught on with GI hygiene regs during WWII + advertising. DuPont created the nylon version you see most places today in 1938.
There are theories (none of which have been corroborated afaik)* that the grain-based diets that caught on with the advent of farming were different enough from our previously evolved diet to cause dental issues; it's part of the relatively recent paleo food movement. The bigger issue has been processed sugar since the 18th century which, yes, played absolute havoc on the teeth of the cultures rich enough to afford it or situated to make it more affordable, starting with the British. Here's a little taste.
*See the posters above and below me: two main and proven issues seem to have been stone particulates in bread as a side-effect of the milling process (not as much an issue now) and continued fermentation of pieces within the mouth which produces maltose, another sugar.
Edit: Here is a history of the US Army's dental programs from a guy in the Surgeon General's office, for the curious. Other sources said it was standard by WWII; this one talks about how many states gave their volunteer regiments brushes and 'dentifrice' (toothpaste) when they set out, even though there were no organized plans to keep them supplied after the first few weeks. It then became standard to wear it in their hatbands as a decoration instead of putting it to its intended use.
/r/askscience has a lot of threads on teeth, such as How long did our teeth last before the invention of toothbrushes?
This is one of those questions that can have infinite answers to represent every culture across time, but FYI, you'll find more responses in this section of the FAQ*
How did people in history clean their teeth?
*see the link on the sidebar or the wiki tab
Maybe you should ask in /r/askanthropology also. They could provide more detailed information than historians can
Diets high in carbohydrates do seem to cause more tooth decay but that becomes more of a science question then a historical one. I can't totally answer your question about brushing but it's safe to say that dental problems have persisted for a long time. Even the oldest civilizations like those found in the Indus Valley have shown evidence of dentistry[1]. So people have been loathing going to the dentist for 9000 years. Flint tipped sticks would have been used to drill into molars and it appears to be common as nine different adult skeletons have been found dating back 7500-9000 years ago.
A reoccuring idea was that people became infected with tooth worms which in turn caused cavities. There have been references made by Homer and even as late as the 14th century when French surgeon by the name of Guy de Chauliac wrote about tooth worms[2].
Sources
"The first mass-produced toothbrush was made by William Addis of Clerkenwald, England, around 1780."
He invented it while he was in prison and it became popular quick due to the rise in sugar imports from the New World, although this factor is not exclusive.
I have no sources so maybe someone can back me up or prove me wrong, but I think when humans began to cultivate grains more we ended up killing an enzyme that lived in our mouths and would keep our teeth relatively clean. I think it had something to do with the sugars in the grain. That's why, I've been told, many "old human" remains still had their teeth.
Here's what I'm talking about I'm probably just doing a horrible job of explaining it.