Here's what I do with our paper mail. This process has been working well for several years.
I bring the mail in from the mailbox. I immediately sort it into three piles - addressed to me, addressed to my wife, and junk to recycle. The recycle pile goes into the recyling bin, my wife's mail goes into her in basket, mine goes into my in basket. Ads and flyers might be junk to recycle and might go in either pile, depending on whether it looks like something one of us might be interested in.
"Basket" is literal - we have "His 'n' Hers" baskets in the dining room that are general purpose collection points. We both drop notes, mail, books, magazines, and whatever into those baskets to hand them off to the other person. (If either of us were the type that leaves socks on the floor, they'd go in there too. They're pretty good sized baskets.)
The mail in my basket then moves to my home office for processing. Bills go in a "Bills to Process" folder (I pay bills in a batch weekly), things to read go in a "To Read" pile. Other mail is handled on a case by case basis. Some gets tossed, some causes me to make entries in my task or projects lists, some goes into a tickler file for future consideration. See http://m.davidco.com/acton/ct/1041/p-0075/Bct/l-0304/l-0304:1d82/ct88_0/1 (PDF) for David Allen's GTD perspective on setting up and using a tickler file.
As I have moved more and more to digital bills, subscriptions, and correspondence, the amount of paper in the mailbox has dropped dramatically. I'm currently averaging less than 5 minutes a day in handling paper mail.