I started my son at five with MIT's Scratch  followed up by Lego Mindstorms .
I then created a text adventure engine  that could run adventures written in a very simple Lua based DSL so he could make a simple text game . Mom helped with spelling and grammar and I suggested a puzzle but he wrote the adventure himself.
Then I transitioned him to Lua on the iPad with Codea  and he (with a little help from me) made a game called StarFighter .
I choose Lua because it is a great intro language. Very simple with minimalistic syntax, few concepts, few primitives, few keywords, dynamically-typed / garbage collected, variable arity, no real gotchas, good tool support, great speed, the ability to access a key in a hash either using bracket or dotted notation, and one of the best programming books for any language (PiL).
But it also scales well; closures, first-class / true anonymous functions, metatables / metamethods, nice simple API for talking between script and C, tail-call optimization, coroutines, short circuiting operators.
But just to give you an idea; he is 11 now and I am learning Scala for work. He's been watching videos with me and I paused it and ask questions and then I asked him where he thinks the presenter is going to go. He ran to his Ubuntu desktop and apt-get'ed Scala and cranked up a REPL session and showed me; he was correct!
I begged my parents for LEGO Mindstorms when I was a kid but we couldn't afford it. I'm hoping that he'll be as interested in learning to code as I was when I was young.