Installing pg gem; ERROR: Failed to build gem native extension

None of the previous solutions worked for me (I just upgraded to Mavericks and updated XCode). Instead, I installed Postgress.app. and called

gem install pg -- --with-pg-config=/Applications/Postgres.app/Contents/MacOS/bin/pg_config

You're right that the problem is related to the Xcode developer tools. It's not a bad idea to make sure you have all the developer tools installed (as opposed to solely installing gcc as mentioned in the previous answer):

1. Open up Xcode
2. In the application menu item "Xcode" select Open Developer Tool > More Developer Tools...
3. This takes you to a site with a bunch of software. Go ahead and download and install "Command Line Tools (OS X Mavericks) for Xcode - Late October 2013".
4. You will now be able to properly install the gem.

For anyone else coming to this issue off of a fresh install of the Postgres 9.3.0 app on Mac OS X Mavericks (i.e. you're not using homebrew for your Postgres installation) you may notice that even though you can build the pg gem you cannot run rake because of a dylib issue:

rake aborted!
dlopen(/Users/[USERNAME]/.rbenv/versions/2.0.0-p195/lib/ruby/gems/2.0.0/gems/pg-0.15.1/lib/pg_ext.bundle, 9): Library not loaded: @loader_path/../lib/libpq.5.dylib
  Referenced from: /Users/[USERNAME]/.rbenv/versions/2.0.0-p195/lib/ruby/gems/2.0.0/gems/pg-0.15.1/lib/pg_ext.bundle
  Reason: image not found - /Users/[USERNAME]/.rbenv/versions/2.0.0-p195/lib/ruby/gems/2.0.0/gems/pg-0.15.1/lib/pg_ext.bundle

Unfortunately this is a problem with the current release version of 9.3.0 of Postgres. Winding back to a previous version will fix it for you:

1. uninstall the pg gem: gem uninstall pg
2. delete your 9.3.0 Postgres app by dragging it to the trash and emptying the trash
3. install version 9.2.2.0 of the Postgres app here: http://postgres-app.s3.amazonaws.com/PostgresApp-9-2-2-0.zip
4. reinstall the pg gem: gem install pg

*Thanks to the comment by jhiro009 on this thread for pointing me in the right direction on this last Postgres app part of the issue although the 9.2.4.3 version that he mentioned didn't work for me.

On OS X Mavericks

sudo ln -s /usr/bin/llvm-gcc /usr/bin/gcc-4.2
gem uninstall pg; gem install pg;

works with homebrew Postgresql (9.3.1) installation and Apple Command Line Tools installed (pg 0.17.0).

Using homebrew fixed this for me:

gem uninstall pg
brew install apple-gcc42
gem install pg

EDIT: I also manually installed "devtools"

xcode-select --install