Though GangstaFeelsGood and AndyLippitt have described good methods for blowing smoke rings, the Big Money lies in a hybrid of the two. I was taught how to blow smoke rings by a true connoisseur — after two hours in a smoking lounge with him, a nice hookah, and a bag of Turkish tobacco, I was puffing out some seriously thick rings with a respectable success rate. Here's what I learned:
Start by mastering Andy's technique: with a mouthful of uninhaled smoke, make an O with your lips and quickly push your tongue forward slightly. (This is somewhat like filling your mouth with water and squirting a stream out — the pressure comes from your tongue moving forward, pushing the water out.) With just a few minutes of practice, you should be able to make a small thin smoke ring.
When you're able to consistently create these small rings, experiment with changing the size of the O your lips make, the speed and force with which your tongue moves, and how much your lips are puckered out. Normally, the more puckered your lips are and the larger the O of your mouth is, the wider and thicker your ring will be, but the harder it will be to create a perfectly round ring (or one at all).
Now you're ready to move on to Gangsta's technique. While you're drawing smoke into your mouth, open your jaw (but not so much that you can't keep your lips sealed). Besides being integral for this technique, this lets you hold more smoke in your mouth, so you will also be able to blow a few more rings per mouthful than with Andy's technique. With your lips in an O, close your jaw slightly but quickly. The first few times, you probably won't make anything resembling a ring — the trick is to keep your mouth in an O the whole time. When you move your jaw, the position of your lips will change slightly too, which messes up your ring. Practice keeping your lips still while your jaw closes, and the rings should come after a while. Again, experiment with the size of your O, how puckered your lips are, and how much and how fast your jaw moves until you're blowing nice juicy donuts.
When you've gotten pretty good at both techniques, you're ready to bring them together. Draw a big puff of smoke, dropping your jaw like in Gangsta's technique. Lay your tongue flat too. To blow the ring, you're going to close your jaw just like in Gangsta's technique, but at the same time contract some of the muscles around the back of the throat. These muscles (AFAIK; IANGA) are what meet the tongue to seal the entrance to your throat (e.g. when your mouth is open but you breathe through your nose). These muscles aren't used much by English speakers, but they're key in the pronunciation of the Hebrew ע and the Arabic ع — as described by Gritchka in his excellent guide to Arabic pronunciation, "the dull metallic tone you get when you slow a choked gargle down so slow that it no longer vibrates." These are the muscles that get sore when you vomit for too long. Contracting these muscles uses the same effect that Andy's technique describes (pushing out the smoke with your tongue), but instead of using your tongue, you're using the muscles at the back of your throat.
This combination of raising your jaw and compressing the back of your throat drastically reduces the volume of smoke in your mouth. All that smoke is pushed out the O of your lips which, because of your practice of Gangsta's technique, maintain their perfect shape. After a few minutes of practice (and more experimenting with lip positions, etc.) you'll be able to consistently puff out thick, evenly circular rings of smoke.
Congratulations!
Gangsta makes a good point when recommending you learn with a cigar: a properly tended hookah will also give you excellent thick smoke for blowing rings (and, IMO, will taste better), but learning how to properly tend a hookah is an art even I haven't gotten down yet.
While they're hard to come by these days, a smoking lounge is the perfect place to master your ski11z. Some colleges (especially in colder regions), airports and maybe even bus stations have smoking lounges. Failing that, the Great Outdoors on a beautiful still day can be delightful — but of course, you need as little wind as possible.
I echo a phrase oft repeated by teachers of just about anything: practice!
Finally, if anyone figures out how to puff a tall ship like that guy did in that movie, /msg me immediately!