I have a nephew who loves Legos. He also dreams (right now at least) of designing video games. A friend (thanks Rajesh!) recently recommended a few great resources for teaching children the basics of programming.
I also tried them out. Baby steps are not just for babies!
Overall I found them to be great starting points, no matter what your age, for understanding programming languages and the building blocks of programming.
If you or your child is already a LEGO fan, then you can gradually scale up in your learning by integrating LEGOs with more realistic components. Try LEGO Technic or a small fun programmable computer Mindstorms.
Finally, there are a few online programming tools you can access. There is a the very visual system designed especially for kids out of MIT called Scratch – some are concerned it doesn’t convey the abstract components of programming.
There is also Python Turtle which teaches children how to program in Python. It’s very simple and more realistic in that a child has to learn to type actual code. Python is considered one of the easier programming languages to learn and many academicians use it. Last but not least is a starter tool for learning Ruby (again another language thought to be easier to grasp) called Ruby4Kids.
Give them a whirl!