Eu também enfrentei esse mesmo problema, o problema é que sua instalação do Linux requer que as bibliotecas de desenvolvimento do PostgreSQL sejam instaladas para construir a gem.
Veja como corrigi o problema
Abra seu terminal e execute os seguintes comandos
sudo apt-get install libpq-dev
E tente instalar o gem PostgreSQL novamente usando este comando
gem install pg
Isso é tudo.
Espero que isso ajude
