Game Maker - cost: $0 for the free version

While it isn't programming by writing code (it's drag and drop actions, though you can use typed code later if you'd like to teach them that), I think it's the best way to teach game development. It's simple to use and quick to learn, but is still capable of creating pretty much ANY video game. Almost any other suggestion will involve knowing a decent amount of programming beforehand and will thus not really work. You'll be limited to 2D unless you want to do serious code, but for a beginner's game you'll most likely limit yourself to 2D anyways.

I started with Game Maker, and from it eventually moved to 100% AS3 Flash game programming, so the skills involved in creating a Game Maker game really do transfer over to other environments.

Pros:
Really easy to learn - no programming knowledge required
Great for rapid prototyping - development is generally much quicker than other environments

Cons:
Limited to Windows (might not apply now, they've been working on it. I think it does HTML5 now.)
Limited to 2D unless you want to teach typed code
In order to do some things, you have to buy the full version (though it's in the $20 per copy range). You probably won't need to buy it at all though.

Dang, it's protected. Anyone know what the WEP key is? I really want to use their WiFi on my moon vacations every other Tuesday.