I use the same ideas as bnich. Using round magnets on a metal staff (you can draw a staff with permanent marker on a baking pan) really helps. My students like poker-chip notes on a cloth or paper staff too.
One thing that seems to be a huge help is having the student DRAW the note. We draw notes on a laminated staff using white-board markers. (Be sure to draw kitty-ears on all middle C's!) Then we play a game where the student has to draw and play the note I call out. Kids love white boards, so this is always a hit.
I will also have my students occasionally compose a simple song in pre-reading notation (SusanParadis.com has great composition activities!) and then transfer it to the staff. Early on, it can be intimidating to draw all of those notes, so we use stickers as noteheads the first few times. Susan's site also has a large staff that prints out at just the right size for chart stickers.

We use dark-colored stickers for quarter notes and light-colored stickers for half notes and whole notes.
You can also turn a really large staff sideways on the piano keyboard so that the lines and spaces line up with the corresponding key on the piano. I measured and drew one of my own on cardstock; maybe someone else knows where to print one out or purchase one.