Wallace:
For a real, no hocus pocus, discussion of the subject, see Vance Packard's Hidden Persuaders.
I did a paper on the subject of subliminal learning/advertising in college. I ended up calling it Subliminal Sophistry, which should give you a clue how I ended up feeling about it. Here's a short synopsis.
The movie theater story is bunk, and the device used regularly malfunctioned. That said, instead of making people want to drink, say, Coke, there is some evidence that if there is a predisposition towards something, the use of subliminal stimuli can successfully encourage certain types of behavior. If someone is a little thirsty, they may be a little quicker to drink water.
There are different types of subliminal stimuli, and we all send/receive subliminal messages that we do not know that we are sending or deciphering. An excellent example of this is body language.
I remember this paper because it was one of the most interesting things I have ever studied, and the paper got an A, with a mention by the professor in class, not because of my writing ability, but because the subject is just so interesting. What an amazing thing is the human mind.