Após algumas pesquisas (em particular this ), acabei instalando vários pacotes:
$ sudo apt-get install gcc ruby ruby-dev libxml2 libxml2-dev libxslt1-dev zlibc zlib1g-dev
Disclaimer: Não tenho certeza de que todos são necessários, mas quando eu os tive, pareceu funcionar.