This works in the US
Call 1-888-5-OPT-OUT (1-888-567-8688), preferably not from a cordless phone.
At the menu, press 3 to opt out permanently (or until you opt back in).
Answer the questions it asks you.
That's it! Within a few days your name will be removed from the list that credit card companies use to send you pre-approved offers.
UPDATE: Turns out there's one more step -- you have to fill out a form they send you, and mail it back to them. Shucks!