One can presume that paleo people used a sharpened twig to clean 
their teeth. Today we have toothpicks. But some cultures had 
specialized twigs. See:

http://en.wikipedia.org/wiki/Miswak

For pictures and to buy, see External Links section.