I gave my kids Scratch:
http://scratch.mit.edu/I've shown them things and written a few cool little things just to play with it. It's a nice introduction into what makes programming "work", ie: "why it's harder than you might think if you've never done it." You can make little sprites and have them move around by chaining logic blocks together. You can take user input, etc..
My kids were only marginally interested but I try to show them things every now and then. I think both my kids have taken a class in it now (my daughter definitely has) and my daughter uses it regularly to draw pictures and record sounds.
My son also took a class using GameMaker.
http://www.yoyogames.com/gamemaker/studio They made a few games in the class but I haven't had a chance to look at them yet since the computer on the main floor isn't running Windows. He hasn't really used it since then but that could be because of access.
(In both cases the classes were at IdeaVentions
http://www.ideaventions.com/ which is a local place we send our kids to cool classes... other areas of the country are bound to have similar places. Kind of expensive, though.)
You can also look at Unity... but as simple as they try to make it, I still think that's the "advanced step" after the other ones go well.