All programming starts with fundamentals that aren't even done on the computer: analysis of the situation, decomposition, reuse, and planning.
Starting a very young age, your child should build up as much empirical knowledge about the world -- an encyclopedia of common sense. Encourage him or her to ask questions and be prepared to answer them as best you can. Let them experiment with physical objects to learn how they interact. What floats? What sticks together? How much weight can you put on something before it breaks? What's soft? What's prickly? What happens when you mix yellow and red? Stay away from the virtual world of TV and the Internet and let them experience the physical world.
Once your child has gained some maturity and is ready to be creative (that is, to create new things), encourage him or her to make some predictions first. Will it fall down? Will it be loud? Will it be brown instead of blue? What happens if you use six widgets instead of eight? You'll be teaching you child about planning and thinking-before-doing.
When he or she is ready to tackle some larger projects (such as cleaning the messy bedroom or planning a picnic), show them how to break it down into smaller projects. Write down a to-do list.
Did something go wrong? Teach troubleshooting skills: retrace your steps; go over your checklist.
All of these real-world skills (and more) will come in handy once you're ready to teach some computer programming. Programming isn't about learning this or that language. No doubt, by the time he or she is ready, we won't be using the same languages we use now. Instead, programming is about critical thinking, analysis, and creativity, all of which have their roots in the real world.