My daughter has been "coding" since she was three and my son since he was two. They began with the code and go robot mouse, where you push arrows in the direction and order you want the mouse to go totally ignoring the course and just trying to get the mouse to the cheese on the floor. Next I bought Cubetto, which comes with a board with pieces that give instructions and you place on the board. Mostly one kid sits on the floor and the other will "program" Cubetto to come over to the them.

Now my daughter is five and plays with Scratch Jr. She makes short clips of characters moving around, recording and timing the characters voices, allowing presents and balloons to magically appear, she's not tying in code but instead uses "graphical programming blocks". She also likes codeSpark.

My kids do not distinguish programming from play. I intend to keep up programming = play which I will later transition to a more advanced version of, "I want to make a thing, writing a program will allow me make it." than what my daughter is currently doing. Make it fun, and don't do much in the way of suggestions/feedback, just let them know you'll answer any questions and let them make mistakes.