I know this has been mentioned before, but its such a great concept, its worth repeating:
If you want BTC to succeed, the single most influential thing you can do is buy 1 bitcoin, and literally send paper wallets containing $10 worth to 80 people you know.
Send one to a wife, and the husband. One for each of the three kids. Send to your house cleaner. Your childrens teacher. Your Vet. Send to your friends, and everyone in their family. Especially their kids. Send to anyone you have any sort of relationship with.
Buy the bitcoin, print out a paper wallet from bitaddress.org and snail mail it to them. Include a note saying "Keep this safe. It may be worth a lot of money one day. You can sign up on "X" exchange and send more value to this wallet address anytime you want."
There is no better way to get people interested in Bitcoin, following bitcoin, and yes - out right promoting Bitcoin, than to send everyone you know a paper wallet.
-B-
And how many of these people would lose the wallets or look at you like you've just given them monopoly money? I think the best way to spread the word is to just tell these people about Bitcoin and plant the seed. Some will be interested, some wont care, and some will think you're trying to scam them or are nuts, but at least you've got the name out there. There's only so long before the masses have to take notice.
For some reason, paper wallets seem to suck as gifts (possibly because "it's a digital currency so wtf are you doing giving me a shitty old piece of paper?"). Who knows. I've had way better experience setting up a wallet on someone's phone and sending them some mBTC. Never fails to impress. A quick poll among my immediate circle of mostly nerdy friends suggests that not a single one knows what a QR code is, even though they see them every day. Most have heard about bitcoins. A bitcoin gift card would probably be the optimum way to impress right now.
They can always import the wallet to their phone. Paper Wallets can be a nice little gift and you can design one to suit them. It's just like a voucher at the end of the day.