I've spoken to a few people about teaching kids to program and am excited to see this new section on DZone!
I have two daughters, 8 and 4 and both love playing on the computer. I run Edubuntu at home and while they love visiting all the online kid sites, they also enjoying playing with more geeky things like TuxPaint (a free graphics program for kids) and some of the educational programs included in Edubuntu. My older daughter has also expressed some interest in what is going on 'under the hood' often times watching me edit config files in the terminal or install applications using apt.
I've got a few things bookmarked for investigation:
While exploring Edubuntu I found KTurtle. It is loosely based on Logo. This looks like an ideal place to start! There is good documentation, a Google Group and it is simple enough for an 8 year old. Plus everyone likes turtles!
Another application I'm going to check out is Scratch. Scratch is a "free programming tool that allows anyone to create their own animated stories, video games and interactive artworks". Unfortunately right now they don't have a Linux version though one is in the works, and there are a few posts on their forum about running it under Wine.
I've also found Hackety Hack which calls itself "the Coder’s Starter Kit". Its built around Ruby and appears targeted at slightly older kids than Scratch (13+).
People have also suggested Smalltalk and specifically Squeak. Both those are a bit too complex for now - but hopefully as we learn more we can move to some more advanced languages.
This year I'm going to try and see if my daughter shows an interest in any of these tools and see if we can explore programming together. I'm also going to introduce her to HTML and let her create her own web page. While many would argue that HTML isn't a programming language I think it will be fun for her to learn.