Call me a cheapskate, but I just can't believe that people are willing to give away 9% to turn cash into...cash.
Whenever the issue of Coinstar comes up, I always mention coin sorting machines like this one.
For the price of about three trips to Coinstar, the machine automatically sorts your coins. When a tube fills up, you slip the coins into a paper roll. No sorting or counting by hand. (For about twice the price of the one linked above, you can get one made out of cherry wood from Hammacher Schlemmer
I've been using a machine like this for years. I empty my pockets straight into the hopper every night, and every few months I take a stack of rolled coins to the bank.