A few years ago I briefly subscribed to
Bicycling Magazine. I don't
think I paid for it; it was some sort of freebie from my
credit card company or something like that. Anyway, I quickly
came to the conclusion that it's primary purpose was to induce me to
shell out for new gear and declined to renew my subscription.
Despite that I continue to receive copies on semi-regular basis,
complete with the requisite occasional threats
about how if I don't pay up I'll stop getting them. Empty
threats, apparently, since it's been years now.
This makes me wonder, exactly what do I have to do to stop
getting the magazine? I realize that the business of magazine
publication is primarily advertisement, but don't the advertisers
want any evidence at all that people actually subscribe voluntarily?

Refuse it.
I get a lot of stuff that I never subscribed too and have no way to stop (see Yellow Pages). I just have a box that this mail gets dumped into and gets put on the curb on recycling day.
(Bicycling Magazine is one of the mags I would pick up when I'm in an airport - its all fluff which I need when I am on a plane)
Same deal with the Newsweek rag
We have had good luck with Catalog Choice (http://www.catalogchoice.org/) Its a free service and has emptied our mailbox of unwanted mail.