Because I have a Ph.D. in computer science, and because my son started computer programming early, I often get asked about how to teach programming to kids. This usually takes the form of asking what programming language to start with.
There are a lot of programming languages out there aimed at beginners, and I have not seen all of them personally. Smartbean has posted a pretty good (though not complete) list with some information about the more popular teaching languages.
There is a long-standing disagreement among teachers of programming about the “best” language to start with. Many CS faculty favor a block-structured language that supports object-oriented programming (typically Java). Many computer engineering faculty favor starting with lower-level language like C, teaching programming simultaneously with computer architecture. Others prefer simplified languages that have few features and are suitable only for introducing programming concepts.
If I were starting with a kid who had no programming experience, I’d start with Scratch, which is available free for Mac OS X, Windows, and Linux operating systems. The system is particularly designed for animations and 2D computer games, though some other types of programming are possible. There are fairly good teaching materials available free on-line as well thousands of example programs to look at (here are some of mine) and kid-friendly discussion forums. The drag-and-drop development environment invites tinkering and play, and it is fairly easy to get simple things working quickly, providing rapid positive feedback that keeps kids interested. The choice of language features in Scratch is a little unusual, as they provide multi-threaded parallelism with message passing from the beginning, but don’t include procedures with parameters (hence, no recursion).
I’ve taught Scratch to kids from 4th to 10th grade and not had the youngsters think it too hard nor the older kids find it too constraining. Mostly the teaching has consisted of a few minutes showing how a particular block can be used, or introducing a basic concept (like turtle graphics, animation by costume changing, or rotation centers), followed by the kids playing with the ideas in their own programs for a few hours. I generally circulate around the room answering questions, which come up much more often if you are at the student’s shoulder than if you are on the other side of the room.