Pax pretty much laid it out. My father started teaching me basic safety rules and proper handling with a cork gun (anyone else remember those?) when I was in kindergarten. He and a cousin of my mother's even took me along on hunts for quail and small game (in clement weather) up near Yreka, CA.
A couple of practical things from my own experience that've worked out well over the years:
The Four Rules are the first thing we cover. It is best made understood that these are Gospel. Deal with any lapse firmly, seriously, and at once. Make it known that a repeat will mean that the day is over, and follow through with the threat. Harsh as it may seem, it is necessary to instill that these are Absolutes.
Whatever you choose to start them out with, make sure it's in proper proportion to their size. It makes everything else go a lot smoother and more quickly if they don't have to cope with machinery way too big for them. $150 for a Cricket, Savage "Cub" or the like is money well spent.
Basic child-sized ear and eye protection is cheap and readily available. Get them, and always set a good example by using your own. Even if hearing protection isn't strictly necessary when using SV shorts or Colibris, it's good policy to get them into the habit of always using it.
Reactive targets help provide the kind of positive feedback to proper execution that captures and holds their interest in the earliest stages. The old shooting galleries had the right idea, and it's a real pity that they've pretty much passed into history. Once they've gotten the message that they can hit a target when they do things right, they usually want to learn how to do it better. That makes the move to paper targets where the positive reinforcement is less dramatic easier.
