sudo gem install pg non funzionerà

Devi installare il tuo pacchetto distro ruby-dev (o devel) altrimenti non sarai in grado di creare estensioni di ruby ​​C.

Non sono su Ubuntu, ma il tuo comando package-manager potrebbe essere in qualche modo simile a questo:

$ sudo apt-get install ruby-dev build-essential