Funny enough, I'm actually a corporate trainer so adult learning is one of the huge focuses of my life, and I had an opportunity to teach someone not that long ago. (3 people actually, all at the same time)
There was a party that I went to with my Girlfriend (She had these blogger friends, and they were all women who brought their husbands/boyfriends with them) and apparently I was designated to be "that guy" that keeps people entertained lol
Anyway, the majority of the people there were pretty naturally like myself in that they were all into things that would mostly be interpreted as "nerdy". In other words: Ideal target audience!
Anyway - like Chris H said earlier, probably the most key important step for any new cuber is to get that it's a 3D object. I took the cube apart and showed them how it works... BOOM for most of them it was instantaneous - they got that the centers never move.
Then I started talking about moves like this:
F = Steering Wheel Right
F' = Steering Wheel Left
R = Right Tire Forwards
R' = Right Tire Backwards
U = Helicopter UP
U' = Helcopter Anti-Up
(That's how I started to introduce notation to them, but mostly just used the verbal association with the movements)
Like Chris said though, the biggest challenge was that everything (for me teaching them) was intuitive except the FRUR'U'F but I just showed them how to exercise OLL control, using RUR'U'. They understood that yellow needs to replace yellow after it's been moved (Hard to explain without more detail here)
Anyway - overall, I had 1 person that I taught to solve the cube in literally 2 hours (while at a party mind you) but it took him around 6-7 minutes to solve. The guy was a phenomenal learner though... He got every concept I threw at him and remembered it almost instantly. (He was also in Med-school to become a doctor so I'm sure memorizing things as fast as possible comes naturally to him!)
There was another guy who took what I showed him, and the day he went home... Solved it later that day.
I was pretty impressed - not really at my teaching but at the fact that they all got it so quickly.
I do agree though that a large part of facilitation is the teacher, not the learner. I mean - everyone is different and while you can use methods that should appeal to most audiences... not everyone learns the same way.
Some people are visual+tactile learners: They need to see and touch it themselves to learn (Which is actually around 60-70% of the majority of the people who learn) but then you still have some people that need to write it down. Some people need to hear it see it. Some need to read it... There are so many various types of learning that could need to be accommodated.
Anyway - I digress.
That's 1 experience though teaching people

I have others, but that was the most recent.