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!