I'll second (or third?) the climber's chalk.
I just happened to have a chalk bag from my climbing days. It's awesome.
I tried out the chalk blocks first to see if there was a difference. There wasn't except that it gets EVERYWHERE.
I felt like an asshole just using it because it is so hard to clean up with just a pinch of chalk.
Seriously consider going to a hippy, outdoorsey type store (Lewis and Clark, Packrat, etc.) for this stuff. I would recommend calling a few rock climbing gyms first though. If they don't have their own "proshop" with better deals, they can tell you where to go to get them for the best price.