On OSX Lion I had to install Xcode and then from inside Xcode install the additional "Command line tools" package (Preferences -> Downloads) to get things working for me.