This is a great article that will help you get started assessing your child
for affinity to martial arts, selecting a school, and long-term success:
Martial Arts Training for Children: A Parent's Guide
Note: Austin Jiu-Jitsu no longer teaches childrens' classes as of 7/31/2011.
This is a brief overview of the wonderful sport of Brazilian Jiu-Jitsu: Brazilian Jiu-Jitsu
This depends on three primary factors: the maturity level of the child, the martial art selected, and what is the parental involvement?
For structured training, 6 or 7 years old is the youngest I have seen consistent success with. Certain kids can succeed at 5, but this is less common.
First, do your research!
If the child is below training age, you can improve your chances of success by beginning unstructured, fun and play in a similar atmosphere to get the kids used to the training environment. With my children, this was easy. I would bring my kids in to watch me train from a very young age (3 or 4 sounds about right). They would play with me on the mats before or after class. This was usually your typical shrieking, silliness, and tickling that was on one hand very fun for everyone, but also got them very comfortable stepping out on the mats. Over time, I would start showing them techniques and bathing them in praise. By the time I opened my own school, they knew all the basics and were a great role model for the new crop of children starting my training. Now, at 8 and 11 they are absolutely unbeatable in their age group. At the same time, they are complete pacifists who would walk away from any chance to fight unless absolutely necessary. In fact, one of the most popular training scenarios I run through is where we role play a bully trying to keep you from getting away. It's ok to walk or run away from an opportunity to fight. I've done it before, and I'm glad I did.
I have a father who trains with me in my adult class. He is trying the same thing with his boy who is 4. His 7 year old daughter has been training with me for over a year in the kids' class. Her little brother comes out and watches. He plays on the mats before or after class. This young man is very shy, but over time I am seeing him slowly integrate with the older kids. By the time he is 6, I am certain he'll be ready. In the meantime, he gets to play on the mats!
I have another father who has 2 boys training with me. They have a little sister who is 3. When she's in the right mood, we get her on the mats before classes where she and her dad can do some healthy roughhousing.
The Martial Art
A key factor to all of this is the selection of the martial art: Brazilian Jiu-Jitsu (a.k.a. Submission Grappling). These kids aren't learning to sock each other in the nose or kick someone in the head. They are learning a grappling sport that involves restraint and control rather than high-impact. It is incredibly effective, yet much safer in that it offers a much broader continuum of force to select from before getting into the danger zone. To learn more, read A Self-Defense Curriculum for Children.