We just bought Typing Instructor for Kids, but haven't started it yet (tonight's the night). It seems to be well regarded here and elsewhere, and I'll let you know how it goes by posting back in this thread. (ETA: As you can see from the links I added, mich's suggestion, Type to Learn, is pretty highly regarded here too.)

If you buy the Mavis Beacon competing product, according to some reviews I read, one or two revs back from the current version is superior.

Here are two previous threads on keyboarding:
http://giftedissues.davidsongifted....1765/Recommendations_for_learning_t.html
http://giftedissues.davidsongifted.org/BB/ubbthreads.php/topics/99272/1.html

ETA: I'm a bit underwhelmed by the Typing Instructor for Kids software. The organization is, in my opinion, the pits.