I'm always receiving financial privacy updates and notices from my credit card banks. I'm not sure if these actually do much, but it's worth a the cost a few stamps. From the back of the latest one to hit my mailbox:

If you prefer not to receive pre-approved offers of credit, you can opt out of such offers by calling 1-888 5-OPT OUT
If you want to remove your name from many national direct mail lists, send your name and address to:
DMA Mail Preference Service
PO Box 643
Carmel, NY 10512
If you want to reduce the number of telephone solicitations from many national marketers, send your name, address, and telephone number to:
DMA Telephone Preference Service
P.O. Box 1559
Carmel, NY 10512

Of course, most people have already heard of the National Do Not Call Registry. Once your number has been registered there a few months, telemarketing calls should become a rarity.