Go to http://postgresapp.com/, download the latest version and install it. At the time of writing the latest is version 93 and the name of the app is Postgres93.app.
Apple Developer Tools
Make sure you have the Developer Tools installed. If you installed XCode you can skip this step.
If you didn't install homebrew before then go for it.
ruby -e "$(curl -fsSL https://raw.github.com/mxcl/homebrew/go)"
Once you are done make sure homebrew is ready to roll.
In my case I had to install the gcc 4.2 compiler but this might not be necessary.
brew install apple-gcc42
And finally install the pg gem specifying the --with-pg-config option:
gem install pg -- --with-pg-config=/Applications/Postgres93.app/Contents/MacOS/bin/pg_config