Madlib é uma extensão do Postgres . Muitas pessoas distribuem suas extensões via pgxn.org , que é como o CPAN ou Rubygems das extensões do Postgres. Então o comando para instalá-lo é este:
pgxnclient install madlib
Depois disso, você pode dizer
CREATE EXTENSION madlib em qualquer banco de dados que você quiser. Observe que você pode precisar instalar algumas dependências primeiro, por exemplo:
sudo apt-get install cmake postgresql-plpython-9.6 pgxnclient
Isso é o que o link de 2013 está dizendo a você, e ainda parece correto para mim. (Observe que mudei o plpython de 9.1 para 9.6.) Tentei instalar o madlib do pgxn no Postgres 9.5 + Ubuntu 14.04, e funcionou.
Por que o pessoal do madlib não distribui um
.deb file:você sempre pode perguntar a eles, mas pgxn é a maneira principal de compartilhar extensões do Postgres. É como ter um gerenciador de pacotes para sua linguagem de programação. 
