El primer paso es identificar donde esta localizado el archivo pg_config.

$ sudo find / -name pg_config

En mi caso el resultado del comando anterior fue:

/Applications/Postgres.app/Contents/Versions/9.4/bin/pg_config

Ahora debemos ejecutar este comando para instalar la gema pg:

$ gem install pg -- --with-pg-config=/Applications/Postgres.app/Contents/Versions/9.4/bin/pg_config

Ahora ya puede continuar con la instalacion de las gemas de proyectos rails sin que veas un error parecido a este:

Gem::Ext::BuildError: ERROR: Failed to build gem native extension.

    /Users/paulomcnally/.rbenv/versions/2.2.3/bin/ruby -r ./siteconf20151202-23808-5nvg49.rb extconf.rb
checking for pg_config... no
No pg_config... trying anyway. If building fails, please try again with
 --with-pg-config=/path/to/pg_config
checking for libpq-fe.h... no
Can't find the 'libpq-fe.h header
*** extconf.rb failed ***
Could not create Makefile due to some reason, probably lack of necessary
libraries and/or headers.  Check the mkmf.log file for more details.  You may
need configuration options.

Provided configuration options:
    --with-opt-dir
    --without-opt-dir
    --with-opt-include
    --without-opt-include=${opt-dir}/include
    --with-opt-lib
    --without-opt-lib=${opt-dir}/lib
    --with-make-prog
    --without-make-prog
    --srcdir=.
    --curdir
    --ruby=/Users/paulomcnally/.rbenv/versions/2.2.3/bin/$(RUBY_BASE_NAME)
    --with-pg
    --without-pg
    --enable-windows-cross
    --disable-windows-cross
    --with-pg-config
    --without-pg-config
    --with-pg_config
    --without-pg_config
    --with-pg-dir
    --without-pg-dir
    --with-pg-include
    --without-pg-include=${pg-dir}/include
    --with-pg-lib
    --without-pg-lib=${pg-dir}/lib

extconf failed, exit code 1

Gem files will remain installed in /Users/paulomcnally/.rbenv/versions/2.2.3/lib/ruby/gems/2.2.0/gems/pg-0.18.4 for inspection.
Results logged to /Users/paulomcnally/.rbenv/versions/2.2.3/lib/ruby/gems/2.2.0/extensions/x86_64-darwin-15/2.2.0-static/pg-0.18.4/gem_make.out