Oh-- one tip that we've learned over the years about music, too:
listen to EVERYTHING. World music, folk idioms, classical, pop, country, big band-- everything.
This is the exposure that means that my DD finds even rhythmically "difficult" or "strange" piano masterworks quite trivial to learn.
I also agree with ashley about age. We found a piano teacher who would take DD before she turned six, but that was unusual-- the key was that she already had quite advanced math and reading skills (she could learn to read music quite well).
Until then, we had a musical instrument petting zoo at our home. My DD loved the recorder when she was two.