Você precisa instalar o servidor PostgreSQL: link
E instale o lib necessário para o pg gem:
sudo apt-get install libpq-dev
Deve funcionar depois disso.
Para o desenvolvimento ruby no Heroku, preciso usar postgresql , mas quando instalo o pacote, vejo esta mensagem:
You need to install postgresql-server-dev-X.Y for building a server-side extension or libpq-dev for building a client-side application.
checking for libpq-fe.h... no Can't find the 'libpq-fe.h header