From what I can tell, the best way to do it is by example, and not by simple logical arguments -- because logic alone often won't cut it.
I'm a bit of a science buff, especially when it surfaces in ways that we can connect with our daily lives. A while back the Science section of the New York Times ran a piece, "A Shocker: Partisan Thought is Unconscious," where neuroscientists used MRI imaging to show what happened to people who had firm beliefs about a given political candidate when they were shown information that contradicted their sympathies. The scientists noticed that the people being studied employed a section of the brain called the cingulate (no, not Cingular), which kicks in when the brain makes judgments for emotions such as forgiveness. In short, if you have strongly-defended beliefs, they're often defended internally with emotion, even if they're also supported outwardly with reasoning.
If there's something to be gleaned about operating-system evangelism from all this (and I use that word deservedly), it's that the best way to get people to switch to Linux may be through something they can get wrapped up in, not just an argument. Arguments about free software are all well and good, but at the end of the day they still remain arguments. For some people, "free" software is like a "free" kitten: it always seems like a good idea at first, until you have to deal with what comes next. But if you're emotionally committed to the kitten (or the program), then the hardships of the litter box and the vet bills (or converting your documents and learning the ins and outs of Linux) won't seem so hard.
Getting people to make that emotional plunge seems to be something that varies widely between people. No two people commit quite the same way -- i.e., not everyone goes to Linux because they're disgruntled with Windows. Sometimes they just see Linux and find something they love that much more, which is great. But by the same token, there are many people who never get there also because of their emotional commitments to an existing setup. They don't want to switch, because, well, they don't want to switch. They've got better things to do than natter about what's running their computer (or so they tell themselves).
I shouldn't completely discount the power of logic here. There are probably plenty of people who made their switch to Linux rationally and don't have an emotional investment in their computers or their OSes. If you ask me, that's how it should be -- a computer's a tool, and to get emotional about whether this hammer is better than that one is faintly foolish. But we're human, and emotions come into a lot of things when we least expect them.
I'm reminded of a Slashdot commenter who described trying to sell an organization on Linux, but the people he talked to kept giggling at the names "Ubuntu" and "Feisty Fawn." Hey, it happens.