I started my kid off last week (he is 23 mos.) I bought him a blow up punching buddy. Blow it up, fill the bottom with water and he beats the crap out if it, the thing keeps bouncing back.
Main thing is to get it started as a game, and keep the play/training short and sweet... By the time he is 4-5yrl he'll be able to learn some simple moves and foot work but it must always be fun and not last more than a few minutes. Never force him to train and don't expect him to be semi- concentrated until he is about 7-8yrl.
PS: The best way for them to learn is by watching, my kid sits and watches me shadow box some times... One day he came up to me and put up his little fists then hit me with a kick to calf and made a "uushhhh" sound the way I do when I shadow box... The next day I bought him the blowup punching toy.