You might consider starting with clapping games, like pat-a-cake. These games are effective because you know when you are out of synch because of your partner. Success is being able to play the game smoothly. The speed can be increased to make it more challenging.
I started teaching my kids by having them press the back of my hands as I was clapping. To them, it felt like they were making my hands clap while I was controlling the rhythm.
Lots of singing and clapping, banging, and dancing to music will naturally support their rhythm development.
EDIT: Ever been to a powwow? There are lots of drums and people are encouraged to clap and stop their feet. Children usually play a role in the festivities.