I just bought a sainsmart 12864 from Amazon and was lucky enough to stumble onto Brad's *duino blog at http://bradsduino.blogspot.com/2012/11/sainsmart-12864-graphic-lcd-display.html
He got me started with the 12864 in just a few minutes.
Copy his real simple script and wire your Arduino to the 12864 with 5 female-to-male jumpers as his blog indicates.
Download the u8glib from the link Oliver provided, and store it in your Arduino library folder.
I just ran the code and it worked. It got me started.
Thanks, Oliver, for posting the link to (your) fabulous u8glib. I'm exploring it now, finding some very nice touches.