My oldest is 9. Considered starting him earlier but wanted to ensure that he could game for at least an hour (he was going strong at 4 hours in!). We played using the Pathfinder rules.
My son played a human Ranger. The youngest, claiming he wanted to "play a ninja", got to run a human Monk 1/Rogue 1 until the lure of his action figures won out.
Since I was unsure what my oldest's first go-round would be like, I dusted off my old UK5: The Eye of the Serpent from TSR which was designed to be run for a party or a single Ranger, Druid, or Monk. It worked out great! My son's about half-way through.
Materials Used:
Pathfinder RPG - My kid really got into the character creation and quickly picked up the basics
Monster Manual 3.5
Eye of the Serpent module
Hot Pursuit Rules from Tome of Secrets - These worked like a charm. My son loved being chased through a forest while pusued by a Hobgoblin and his three hunting dogs!
I also used Reserve Points from Iron Heroes/Unearthed Arcana to maximize survival chances and compensate for the lack of magical healing.
Obviously, with no spell-using PCs or NPCs, the learning curve stayed pretty low. He quickly caught on to attacks, HP ("you mean it's like your health bar in a video game?"), damage, saves, and skills. It was also a big deal when he got to use a different dice ("cool, I get to use the 10-sided one") which made me smile.
All-in-all, it exceeded my expectations which I felt were pretty high to start. He's already tossing around ideas for his characters backstory, things he wants to do with his loot, etc. I think perhaps the coolest part about it is that he requires little story-motivation other than "it'd be cool to explore that". That's something that's sometimes hard to come by in my normal adults-only campaign.
P.S. In case the "gorgeous book" praise for Pathfinder needed any reinforcement, my little one asked if we can look through the Pathfinder RPG pictures as part of the books-before-bed routine.