I take the pennies in the “have penny leave a penny, need a penny take a penny” dish and put them in cronological order. Then I stack them with the oldest on the bottom and newest on the top. I know… they aren’t paying me nearly enough.
When I’m board at work, I get on the Board. At work.
Good one, Duke! 
Well, when I had a functional laptop, I did the board thing often. I didn’t even have to be board. I loved the board. I miss the board at work. Nothing like it, when you are board.
Now that the laptop has taken a dirt nap, no more board. I draw (I now bring my whole set of colored pencils to work) and I read. I read a lot. I draw a lot. (I have the kind of job where this is perfectly acceptable. There is a “babysitting” aspect to our job, so we all bring stuff in to do.)
I’m bored at work right now, and this is what I’m doing. Does that answer your question? Oh yeah, and I take lots of smoke breaks.
I’m currently at the first job I’ve ever had where I’m never, ever bored. I go in and start working, and I work like hell until quitting time, and I go home. It’s great.
Clarification: I’m not there right now; I’m at home right now.
I don’t get bored at work, because I don’t have the time. I’m always busy working.
I surf the web, go harrass my coworkers, or go read the local paper in the office library. Sometimes I read The Chronicle of Higher Education online, which is still working I guess since they want me to know what the hell is going on in the world.
I ought to be cleaning my office, working on my dissertation, updating my wedding websites, or pursuing some research projects I’ve been pondering.
But I don’t.
When I’m bored at work, I leave early!
Doesn’t happen too often. 
I also work like hell from the minute I get in, in hopes to get out BY quitting time. I love my job though.