All good suggestions so far. When kids tire of Alice and Scratch because they are just not challenging enough, I highly recommend the book
Computer Programming for Kids and Other Beginners
Warren D. Sande and Carter Sande (Manning Publication)
It teaches introductory programming using the Python language. Another resource for Python is the wordpress blog:
Two additional books I have not tried are open source by Al Sweigart here: http://inventwithpython.com/
The advantages of Alice and Scratch are obvious. It's graphics and fun pictures that are manipulated with little or no actual coding involved. But it is insufficient for really learning to code. Good luck!
When my son was 7 years old I gave him a copy of the book "The Game Maker's Apprentice" by Jacob Habgood and Mark Overmars. I had to sit with him for the first couple of chapters, and then he was able to work from there with progressively less supervision and assistance. He was a very good reader and needed a bit of hand holding with some of the mechanics of starting a program, saving a file, and navigating around. The book uses the free version of the software until the last section of the last chapter--so once you have the book there isn't any additional expense. Alternatively there are online tutorials that use the free version. The advantage of the book is that it is well structured for beginning students of programming and it comes with a resources CD that has provided endless hours of source material for his own games. The authors have had lots of experience teaching kids to program and the book does an excellent job of getting some very key programing points across, from simple if..then..else, to loops, to rudimentary artificial intelligence concepts that make games more exciting. The book isn't just a collection of recipes either, but challenges the student to add their own features and flair to each program. An older child that has been swimming in commercial video games might not be that impressed with the games--but the key point of this is to become a creator of programs. The book not only covers the programming aspect, but also making graphics and sounds (and has some great recommendations for open source tools).
Game Maker has a drag-and-drop style interface which helps children come up to speed with the events and processes associated with programming a computer. Towards the end of the book the scripting portion of GML is introduced. By the end of the book the child will not only understand the logic and processes of programming, but will also be exposed to scripts and functions written using a text editor. Overall I have been very impressed with the structure and learning content of this book. It took about 9 months to make it through the entire book, most of it without parental assistance other than play testing each game, assisting with debugging when necessary (but the book does a good job of trying to instill this skill as well). Along the way there were simple home brew games that have led to more sophisticated home brew games. A few months ago I finished play testing Zombie Fight IV. It has been three years and many homemade games later I can only say I got my money's worth.
It is thrilling to see my son enjoy the creative process of making a game of his own design, getting me and his friends to play test it, and then come up with new ideas and add to the game. He is not a consumer of computer entertainment as much as he is involved in the creative process. It seems he no sooner finishes one game than he has even better ideas and starts working on the next game. This summer it is Zombie Fight V. One of my favorite games he did was a two player aerial combat game based on Wingman Sam from the book, but extended. He and I can play this game for many minutes, side-by-side helping each other through progressively difficult boss levels. He spent weeks on this one.
When he was 9 years old we got the Pico Cricket--which I think is a fantastic learning toy. He did use it for computer control of his last science project. He was able to think through the programming needs and easily write the program to control the experiment, collect and display the data both on the LED display and on screen. He doesn't enjoy this as much as I would have hoped. The Pico Cricket has tremendous untapped potential--it can be used with almost any construction toy we have in the house and it has great potential in making kinetic art. I find the programming language a bit restrictive. The project involved reading a hall sensor when a magnet was nearby--and while he was able to accomplish this with the programming language it was difficult to get across the concept of "real-time", let alone enforce it with the code.
Last summer we bought an Arduino. The GML scripting language of Game Maker is excellent preparation for the more "C" like style of the Arduino sketches. I haven't found anything compelling enough to get him excited about the Arduino--he is much more excited about making his own games--which is entirely OK. Blinking LEDs can only hold the attention for so long--but mummies wandering around a pyramid maze--well that is a lot more exciting.
This summer I am going to try the Modkit Micro environment with the Arduino and we will have a father-son activity building a robot (Popular Mechanics magazine Feb 12). I am hoping this will be excitement enough to get out of the game programming world and light a fire of excitement for programming in the world around us.
You may want to look at the demo of Construct 2, which allows you to create games in HTML5.
Sadly, unlike gamemaker, it does not allow for things like scripting. But it may in the future, considering it's relatively new and there is an update every two weeks it seems. :D
I would recommend two apps for those with iPads or other iOS devices. Cargo-Bot is the first app programmed entirely on an iPad and it teaches the logic of programming in a way that's easy for young children to grasp. It's also free. Move the Turtle - Programming for Kids is a great place to start too. They both target slightly younger audiences than something like Code Academy, but they are also ideal for independent use. They won't necessarily teach you how to build a website right off the bat, but they will get you to "think like a programmer," and I think that's the hardest part to teach.
I highly recommend the book "Andre Curse" by Omi M. Inouye (I found it at Thinkgeek personally). It is a fun little book and can really help the kid to grasp a lot of basic concepts in programming (Primarily it is about Recursion).
Other than that, lots of nice suggestions so far which provide you with premade tools. My best idea was to start him out in Java, but build a lot of libraries for him so that there are many incredibly simple commands available to him which will have hefty results. As he desires to customize outside the bounds you set for him, allow access to the libraries in increasing levels of depth/complexity.
Inexpensive (free) and fairly easy to learn languages are out there but ones that have gateways to more powerful languages are rare. Sure, LOGO is fun and you can learn some of the concepts like loops and variables but I've never seen anyone using LOGO in a work environment. Enter Karel. http://www.stanford.edu/class/archive/cs/cs106a/cs106a.1124/handout... Karel the Robot Learns Java is an easy to use, free, resource which is used by the Stanford programming course to teach students an introduction to Java programming. I believe you can download the online course videos from iTunes U and I used it to teach my son an introduction to Java. Starts out fairly easy, four basic commands, builds on it and eventually you have him doing some fairly decent stuff. The real gem here is that it's Java and once you graduate from Karel to Java you know enough Java to make a fairly decent go of it.
Having taught my son Java programming using this resource I can offer a few tips which should apply to any programming teaching.
1. Do it first. Spend the night before working out the solution to any of the problems/homework/applications so you know how it works and what possible pitfalls there are.
2. Let them make mistakes. Part of programming is debugging. Although it's hard to watch someone make an error and resist the temptation to correct them it's necessary if you want them to be good programmers. Let THEM solve it. Help, but don't do it for them.
3. Come up with a Fun project. The Stanford class creates a Java application which builds the old Breakout game. Having a game you can play (or let your friends play) is pure joy at the end of a long day of math, logic, and debugging. "Hello World" is great for day one, but a challenge and a goal is necessary for long-term interest building. Every new concept can be linked to this final project... "This is how you make a rectangle with GRect, now what would you get if you made 50 of them side by side? Your brick wall for Breakout!"
4. Drag and Drop is not programming. It makes a program, it teaches some of the basic concepts, but it doesn't enforce Syntax or teach them debugging or translate into a real-world programming experience. Don't shortcut. Real programmers code.
5. Keep it short. Just as a programmer gets tired after staring at code all day long your little one will get tired very quickly. Don't discourage him by making him do a marathon programming stint early on. Small goals, build upon them, take breaks. Some basic rewards should be inherent like seeing the ball bounce on the screen for the first time but other rewards can also come with major accomplishments. "Nested loops are tough! Ice cream anyone?"
6. Have Fun! Make sure they do as well.