Dental plaque is a biofilm made up of bacteria adhering to the enamel surface of the teeth. Plaque is soft but over many days can gradually calcify. The hardened plaque, called calculus (or dental tartar) can build up in layers. This forms an ideal surface for further plaque formation and can damage the connective tissue between the teeth and gums -- so dentists and dental hygienists work hard to remove tartar.
Despite these risks to dental health, calculus formation is a natural process in populations of humans and animals. Teeth from archaeological sites often have calculus adhering to them. This calculus contains partially mineralized bacteria, organic material, epithelial cells and fragments of foods ingested by the individual during her life.
Recently, archaeologists and paleontologists have begun to examine calculus samples microscopically to identify the traces of ancient foods. Phytoliths are microscopic structures made of silica or calcium oxalate, many of which are distinctive to species or genera of plants. These durable inorganic structures can persist for hundreds of thousands of years. Many kinds of plants store their starches in granules that can also persist over long periods of time. These granules differ in form among families of plants. Starch granules also display characteristic changes when they are heated or cooked in liquid. Hence they can provide evidence of cooking practices by ancient people.
Amanda Henry and colleagues  scraped a bit of calculus off the teeth of Shanidar 3, from the north of Iraq sometime around 50,000 years ago. This skeleton is housed at the Smithsonian National Museum of Natural History, and figured in the 2009 story about a projectile wound between its ribs ("Real stories of the Neandertal CSI"). The Shanidar skeletal remains are generally called Neandertals on the basis of their morphology. This case is better for Shanidar than for near-contemporaries in the Levant such as Amud or Kebara, and may reflect connections with populations to the north in the Caucasus. No genetic sampling has been done on the Shanidar sample.
Neandertals are known for a diet stereotype -- they ate a very high proportion of meat. This stereotype is rooted in fact: the majority of Neandertal sites show a clear reliance on large mammal acquisition. Bison, horse, red deer and other large mammals are represented, often with a statistical preference toward one of these species at a given site. The faunal remains from many Neandertal sites are consistent with an ambush hunting strategy, with a higher proportion of prime age adult animals than found among persistence hunters or scavengers. The stable isotope record in Neandertal teeth so far seems consistent with an estimated 90% or more meat consumption, leaving relatively little dietary intake from plant foods.
This is an odd picture for a hunter-gatherer: all hunting and little gathering. Most living hunter-gatherers rely on plant foods to buffer the risks of hunting. Many eat far more calories from plants than from meat. Plant processing in the archaeological record is well-known from among the earliest archaeological traces ("Plant processing with early Oldowan tools") and continued throughout the Paleolithic. The question at hand is specific to Neandertals -- how dependent were they on plant foods, and how much would they have been specifically adapted to meat acquisition and consumption? Some high-latitude hunting groups, such as the Inuit, do maintain very high meat consumption, and the Neandertals may have relied on this strategy in Europe.
In contrast to Europe, a pattern of plant exploitation has long been known in the Middle Paleolithic of the Levant, at sites like Amud and Kebara that many argue were occupied by Neandertals. For example, Marco Madella and colleagues  describe phytoliths from the soils of Amud Cave. They demonstrated that these people were probably gathering seeds from grasses, systematically enough to concentrate the phytoliths from mature grass panicles in the sediments. Efraim Lev and colleagues  described charred plant remains including legumes and pistachio nuts from the Mousterian levels of Kebara Cave. Middle Paleolithic people in the Levant were using plants in quantities as great as can be shown at any contemporary sites anywhere in the world.
Henry and colleagues help to put the seeds in the mouths of the Shanidar Neandertals. The Shanidar 3 calculus samples yielded substantial evidence of barley consumption. Many of the starch granules were clearly cooked:
The overall pattern of damage to the starch grains matches most closely with that caused by heating in the presence of water, such as during baking or boiling, rather than “dryer” forms of cooking like parching or popping (38). The finding of cooked Triticeae starches on the Shanidar teeth reinforces evidence from other studies (13) that suggest that Near Eastern Neanderthals cooked plant foods.
They report that 42% of the starch granules on these teeth are consistent with damage from cooking, suggesting that cooking was a systematic strategy for plant exploitation in these people. They also find other plants besides grains -- including legume seeds and tubers of some kind, and phytoliths from date palms.
In addition to the Shanidar 3 skeleton, Henry and colleagues examined calculus samples from the two skeletons from Spy, Belgium. This gave them the opportunity to examine plant consumption in a European context. These teeth included starch molecules in relatively large numbers, mostly derived from some kind of plant underground storage organs (USOs) which the authors tentatively identify as a water lily. At least one starch granule of a sorghum or related grass seed is also present, along with a few other unidentifiable starches and no phytoliths.
The authors cannot conclude much about the importance of these plant foods to the overall diet. The remains of starch grains and phytoliths tell us about diet breadth but not the proportions of different foods. They do note that nitrogen stable isotopes are most informative about protein-rich food sources, so that a substantial consumption of starchy plants such as grains and USOs might be hidden by isotope analysis. Their main conclusion is about dietary flexibility and the sophistication of Neandertal foraging strategies:
These lines of evidence [cooking and processing of grains] indicate Neanderthals were investing their time and labor in preparing plant foods in ways that increased their edibility and nutritional quality (24, 45). It should also be noted that date palms and possibly other un- identi␣ed plants have different harvest seasons than barley and legumes, a factor that may suggest that the Shanidar Neanderthals practiced seasonal rounds of collecting and scheduled returns to harvest areas. Overall, these data suggest that Nean- derthals were capable of complex food-gathering behaviors that included both hunting of large game animals and the harvesting and processing of plant foods.
I expect that quite a bit more evidence from dental calculus will be forthcoming. The study of microfossils from a broader range of sites will help to give a picture of the local resource exploitation. It may not be possible to get an estimate of dietary proportions from these kinds of evidence, but I imagine that similar comparisons of calculus samples from other animals will provide some useful context for the human numbers. In addition, calculus has become a promising source of DNA recovery, from the epithelial cells trapped in its calcified matrix. This has a good chance of recovering ancient DNA from specimens that have not previously yielded any successful extraction.