How to stop junk mail in three steps, as gleaned from recycleworks.org:

1. Hit the big dogs first
Write two letters. One to: Harte Hanks Direct Mailing, Circulation, c/o Pennysaver, 2830 Orbiter St., Brea, CA 92821. The other to: Valassis Direct Mail, Inc., Consumer Assistance, PO Box 249, Windsor, CT 06095. On each, ask for your name to be removed from their mailing list, and make sure to give them all variations on your name (Beth, Elizabeth, Betsy, etc). For template letters, click here, and here.

2. Hit the medium dogs next
Contact Direct Marketing Association (DMA), and get off their list. Online seems easiest, though it requires a credit card to "confirm your identity".

Opt out of credit card offers by calling the opt out number: 1-888-567-8688. This, I believe requires your Social Security Number, but I assure you it's legit.

Opt out of Publisher's Clearinghouse by calling 1-800-645-9242.

Opt out of shopping flyers:
      ValPak Coupons: 800-237-6266.
      Advo/Valassis: 888-241-6760, or online at www.advo.com/consumersupport.html.

3. Get catalogs gone
You can opt out of some catalogs by going to catalogchoice.org.