Scratch is really great. It's free, and kids can publish their work online. Being able to see what other people are doing, tinker with their work, and show off your own projects was a big draw for my son.

It's a visual programming environment, so moving into a second more traditional (text-based) programming language is a non-trivial step, but scratch gets you thinking in terms of algorithms, teaches about what variables are and why they matter, loops and conditionals, etc.