También enfrenté este mismo problema, el problema es que su instalación de Linux requiere que se instalen las bibliotecas de desarrollo de PostgreSQL para construir la gema.
Así es como solucioné el problema
Abre tu terminal y ejecuta los siguientes comandos
sudo apt-get install libpq-dev
Y luego intente instalar la gema PostgreSQL nuevamente usando este comando
gem install pg
Eso es todo.
Espero que esto ayude
