I have probably taught around three dozen absolute beginners how to play go over the last few years between club promotion tables and cultural events at my university. I have found the most important thing is to get them started playing a game.
My current formula/plan is to teach them the rules using basic examples:

This is capturing
- Click Here To Show Diagram Code
[go]$$Wc This is capturing
$$ ---------------
$$ | . . . . . . .
$$ | . . . O . . .
$$ | . . O B O . .
$$ | . . . 1 . . .
$$ | . . . . . . .[/go]

This is also capturing
- Click Here To Show Diagram Code
[go]$$Wc This is also capturing
$$ ---------------
$$ | . . . . . . .
$$ | . . . O O . .
$$ | . . O B B O .
$$ | . . . 1 O . .
$$ | . . . . . . .[/go]

The diagonal doesn't connect
- Click Here To Show Diagram Code
[go]$$Bc The diagonal doesn't connect
$$ ---------------
$$ | . . X . . . .
$$ | . X W X O . .
$$ | . W 1 . O . .
$$ | . . . , . . .
$$ | . . . . . . .[/go]

This is 4 points for white
- Click Here To Show Diagram Code
[go]$$Wc This is 4 points for white
$$ ---------------
$$ | . . O . . . .
$$ | . . O . . . .
$$ | O O O . . . .
$$ | . . . , . . .
$$ | . . . . . . .[/go]

This is a ko
- Click Here To Show Diagram Code
[go]$$Wc This is a ko
$$ ---------------
$$ | . . . . . . .
$$ | . . . O . . .
$$ | . . O B O . .
$$ | . . X W X . .
$$ | . . . X . . .
$$ | . . . . . . .[/go]
After that, I play a game with them. If they are curious how to proceed I'll tell them the basic idea of corners-sides-center. During the game I try to find common beginner mistakes and point them out so they see how the stones work.

These stones get captured
- Click Here To Show Diagram Code
[go]$$Wc These stones get captured
$$ ---------------
$$ | . . . W W X .
$$ | . . a W X X .
$$ | . . O X . . .
$$ | . . O X . . .
$$ | . . O X . . .[/go]

This is a ladder
- Click Here To Show Diagram Code
[go]$$Wc This is a ladder
$$ ---------------
$$ | . . . . . . .
$$ | . . O O . . .
$$ | . O B B O . .
$$ | . . O , . . .
$$ | . . . . . . .[/go]
After the game I talk about scoring again. I show them territory scoring. I explain how dead stones work and how you can move stones in your territory to get boxes.
Then, if others are there, I try to get two new players to play a game and I monitor it. If there is any confusion about rules I'll let them know. Usually, two beginners are quite capable of playing several games.
For example, at my university's Global Games event our club taught Go and Shogi to fellow students. One guy played 5-6 games of go on a 13x13 board against 3 different opponents not including myself. He was able to teach one opponent about ladders after I had explained it to him in our first game. Yeah, all the players made a lot of mistakes, but they also learned a lot of moves through playing that they thought were fascinating because they discovered them themselves.
My goal when teaching beginners is not to teach rulesets or amazing strategy. I only want them to like the game and I think the most important thing to do for that is to get them to play games - so I try to move quickly into playing and not spend more time than needed on rules. If they have questions about these things I will teach them, but otherwise I let them discover tactics on their own.