My sister just made a whole bunch of those heatable bags for her friends. A skull and crossbones-shaped one, a bunny shaped one, some featuring Asian icons that I don't recognise. They are adorable! You could make her one and pretty it up.
Also, I think red or black panties are a great idea! Try stenciling them with pics of tampons, chocolate bars, bottles of Pamprin, or anything else that has to do with menses.
You should also make her a little card that says "Happy Menarche!" with a pic of a uterus. Speaking of uteri... http://knitty.com/ISSUEwinter04/PATTwomb.html
I've been meaning to make one of these...