Basically, the game is broken into stages. Start with the first stage, First Capture, where the winner is the first player to capture one or more stones. Play a few dozen or a few hundred games -- which will take very little time; only a few minutes per game. Play First Capture on a 9x9 board; start the game with two black stones and two white stones already on the board near the center, in a cross-cut formation. The point isn't to win, so discourage the players from pondering long and hard (plenty of time for lengthy ruminating later). The point is to learn how to capture and not to be captured, and to build a mental library of recognized patterns, and to gain experience quickly.
When First Capture is ending in draws or becoming dull, move to the
next stage, Capture Five. Just like it sounds, the
first player to capture 5 stones or more, wins. The stones can be
captured one at a time, or in groups -- it doesn't matter; the point
is to capture five stones. At this stage, sacrificing stones
becomes a viable tactic. You can give up a stone or two if, in the
process, you capture enough to win. Also, at this stage, ko
will probably happen (seki might happen too, but it's
less common). It is best if an experienced player is present to
explain how it works. And finally, the coolest thing that happens at
this stage is that, after several dozen games, without being told
about "eyes" or "living groups" or other fundamental
(yet initially confusing) go concepts, players start two make
living two-eyed groups, all on their own. Eureka!
Now, move on to the third stage, Capture Most. The player who captures the most stones is the winner; if nobody captures anything, then it's a draw. New players probably don't need to spend much time at this stage, because it is essentially go, just with a different criterion for recognizing the winner.
Now, the neophyte is ready for full- fledged go, where the winner is the player who has the most territory after the prisoners are repatriated and the score is counted. She or he has a much stronger grasp of the fundamentals -- shape, life and death, corner oddities, the dangers of the edge, elementary tactics -- than the player who just leaps in with instructions to "make two eyes." That is the beauty of the Capture Game.
Despite the excellence of Mindy's .gifs and explanations, one day Real Soon Now (in other words, don't hold your breath), i plan to use Hiroki Mori's excellent go utility, GoodShape, to generate some java applets which will demonstrate the Capturing Game.