We did some piano lessons pretty early, I think my son was an older 3 when we started. I did not want suzuki for him because he was reading and I thought he would enjoy learning to read music. I had to really search for a non-suzuki teacher that would take that age. It all depends on the teacher. This teacher spent only stretches of a few minutes actually at the piano. They had other activities such as a big floor mat with spaces and lines (a staff) and would play twister (put your hand on a line, now your foot on a space, etc). Or jump on a space, now on a line (later jump on the c note, etc) They had music bingo, and a computer game to learn names of notes. They would go from activity to activity with momentum and an air of fun.

If you call music teachers ask if they have experience with the age group and examples of what they do during lessons.

The books we used were from http://www.musicforlittlemozarts.com/ You can even buy the characters.