Pour installer la gem postgresql sur une version de type Debian, il faut installer les outils dev de PostGres :

sudo apt-get install libpq-dev