Oooh... I like it when you touch my avatar.
A new contributor on my blog just posted a great article about teaching Magic: The Gathering to new people. Here's a link:
Dos and Don'ts For Teaching Someone To Play Magic: The Gathering
I've taught a lot of MtG to high school kids and to a few friends of mine. The article is pretty good, with only a few quibbles here and there for me.
The most important thing is the part about using simple decks, which I absolutely agree with. I actually don't think any of Wizards' premade decks are all that helpful here - Core Set Intro Decks are probably the best thing available, but they have a tendency to include a broader variety of cards than necessary and to run two colors, often for little good reason. The "giveaway" Planeswalker decks are OK, though they're maybe a little too boring and aren't available everywhere. My favorite training decks are monocolor M10 decks I built long ago for this very purpose, and they work perfectly. I have one for each color.
I disagree about non-land mana sources in the specific case of Llanowar Elves. Green Ramp is a fundamental archetype of the game, and the good old Llanowars are an iconic ramp creature. I wouldn't include any non-land mana beyond them, though, and definitely no special lands.
I include one artifact in each of my decks, though I can see the case for excluding them. But I think they add depth, and I like even my training decks to have enough depth that I enjoy playing them too. Definitely no Planeswalkers, though.
I mostly agree with making decks creature-heavy, except in the case of Blue. If you're going with monocolor decks, Blue should certainly be the one to show what control archetypes look like. That means that someone's first game should be with another color, though. I never let a new guy play Blue until I've played it against him, and I never play it against him for the first few games.
I agree with no tap effects, though that's a classic effect too. The timing issues there only make things too complicated for a beginner.
I agree about theme and including cards that work well together (obviously). I would also add that a good beginners' deck shouldn't be full of one-of's and two-of's like the Duel Decks. Besides being a lot of card reading and processing for a new player, you want a good starter deck to be one where the player can learn how to pilot it better over the course of a few games. It's hard to improve your strategy if you're seeing a ton of new cards every game.
I disagree about not explaining the stack. I understand that this can maybe be intimidating, but it's totally fundamental to the game. I always give the basic example of Giant Growth and Lightning Bolt on a small creature, and how the result changes depending on what was cast first. I've never had a problem with that, though I wouldn't go into any further detail.
Again, by far the most important element is having good training decks. The rest is largely a matter of teaching style and personal taste.
For my teaching decks, I followed similar patterns. I decided to go with 3 copies of most cards in each deck (at least the iconic creatures and removal) so that the new player does not have to see new cards all the time, it is important to start recognizing them from their image. Definitely 40-card decks, much more focused.
Of course the above reduces variety, so I went with two decks for each color, demonstrating to some point the different strategies each color follows. For example, for blue I have a beatdown Melfork (with bounces and fast creatures) and control Flying (with counterspells and removal)
I preferred cards with no text (those 5/1 crocodiles and snakes were sitting anyway) or cards with 1-2 lines of text