Reuters tells us that Neandertals used toothpicks:
Two molar teeth of around 63,400 years old show that Neanderthal predecessors of humans may have been dental hygiene fans, the Web site of newspaper El Pais reported on Tuesday.
The teeth have "grooves formed by the passage of a pointed object, which confirms the use of a small stick for cleaning the mouth," Paleontology Professor Juan Luis Asuarga [sic, should be Arsuaga] told reporters, presenting an archaeological find in Madrid.
The fossils, unearthed in Pinilla del Valle, are the first human examples found in the Madrid region in 25 years, the regional government's culture department said.
I guess the press was struggling to think of something interesting about those teeth. But toothpicking is nothing new. The first evidence of these interproximal grooves is nearly 2 million years old! Leslea Hlusko (2003) gives a nice review, and shows how the grooves can be made fairly quickly using grass stalks, which are embedded with hard opal phytoliths. Her article has an easy moral: Don't floss with grass!
A bit of context would inform people that all early humans had good dental hygiene, at least by the standards of recent agriculturalists, because tooth decay was exceptionally rare. This is mostly due to the absence of sugars and readily digested starches in ancient diets, but also may be attributable to an increase in the numbers and virulence of oral pathogens.
But it's cool that they found a new hominid-bearing cave in Spain. If that date holds up, it's a very interesting time -- substantially before the youngest Spanish Neandertals. Hopefully they'll find more!
Hlusko LJ. 2003. The oldest hominid habit? Experimental evidence for toothpicking with grass stalks. Curr Anthropol 44:738-741. doi:10.1086/379263