Nothing? Or do you scribble on them?
My family has developed a tradition of playing hangman while we wait for our orders. We’ve gotten some good words at times. Things like “lynx”, “lengthwise”, and “linguist.” (My dad got into an indigent huff when my visiting roommate did “scry”. I’m still not sure he believes it’s a real word). (Tonight I think I’m going to try “psalm”. I’ll see how that goes).
I keep track of the waitstaff’s score according to my point system.
No, not really. I can’t think of anywhere I’ve been in ages that had paper placemats. I love the Hangman idea, though.
It’s rare that I eat at a place with paper placemats, but when I do I make origami frogs, guns, airplanes, etc out of them.
I can’t wait to get to the really fancy stuff so I can start leaving those behind.
I don’t do anything with them. However . . .
In June of 2010 I was traveling from Chicago to Seattle on the Empire Builder. My tablemates at dinner the first evening were a woman and her two daughters who were returning from her parents’ in Ohio to their home in Kalispell, MT. Before the meal was served (and during most of the rest of the time) the younger girl was drawing in crayon on her placemat, with all the tongue-sticking-out concentration a four-year-old typically applies to the task. At the end of the meal she solemnly presented me with the completed work, for which I just as solemnly thanked her. And I still have it.
(I imagine that to some, my keeping the placemat marks me as some kind of stalker and/or obsessive. But to me it’s a reminder of a gracious gesture from someone who was too young to know the word.)
I draw cartoon animals on them.
I use them as foundations for my sugar-packet pagodas. They have higher friction than most tables.
Update: Two brothers in tandem are a terrible thing. I didn’t even get up to the second arm with “psalm”. 
I crumple them up and toss them to the floor and when the waitress asks if I would like another paper placemat with the maze on it, I say, “Please.”
I draw naughty, naughty pictures on them.
Naughty.
My mother’s display of Pics from the Grandkids includes one from a 3yo boy who “adopted” her on the train.
I don’t normally do anything with paper placemats other than read them; I have one I kept from a Chinese restaurant, which explains the Chinese zodiacal signs. Back when the Bros were little, we sometimes used one to play hangman-style games.
This made me go “awwww”.
And this made me go :D. I will have to mention this to my nephew, who might be old enough to be a father but is determined to never grow up.
I was going to say the same, but decided that I’d be looked down upon as being a snob. But then I remembered, almost all of the Chinese restaurants (back home in Michigan) have paper placemats. Even the “nice” places. You know – with the Chinese zodiac.
So my answer is, I read them until the food comes. (I’m a Pig, for what it’s worth.)
I use mine to jot down calculations of obscure problems in quantum mechanics.
I also autograph them to give (in lieu of tips) to the waitstaff.
I once drew an elaborate scene where the waitress had enough and began mowing down the patrons with a machine gun. That got me a free mexican ice cream.
My husband and I are engineers. Therefore, our paper placemats, and often our paper napkins, have ended up with drawings on them. Sometimes it’s an idea for something we’re doing at the house or on our boat, sometimes he’s showing me something he’s working on or a problem he needs to solve, sometimes it’s just an engineering flight of fancy.
He told me about one place he visited for work where the facility cafeteria provided scrap paper at each table to keep the engineers from drawing on the napkins and placemats. In a similar spirit, I try to keep paper in my purse for those restaurants that don’t do paper mats…
I liked the placemat at one restaurant so much – it was a line drawing of the outside of the building – that I took it home and framed it. It’s hanging in one of the bedrooms, and doesn’t look like a placemat at all, but a piece of art.
Do it with dollar bills, much more effective.
We play Sprouts. My 7 year old is a killer at Sprouts; I may have to teach her the Misère form to have a fighting chance again.
I’m not an engineer, but I always have a notebook (dead tree) and pens in my purse. In fact, I have a variety of pens in my purse. I have one pen that has 10 colors in it. Perhaps I SHOULD be an engineer, because I know that this particular pen is the envy of every engineer.
I hope he wasn’t the one paying the bill at the end! 
But yeah, my family always draws or plays games on paper place settings or tablecloths. “Dots and boxes” used to be a favorite.