O arquivo pgfplots.sty
deve ser fornecido pelo pacote texlive-pictures
em 14.04
$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=14.04
DISTRIB_CODENAME=trusty
DISTRIB_DESCRIPTION="Ubuntu 14.04 LTS"
$
$ dpkg -S pgfplots.sty
texlive-pictures: /usr/share/texlive/texmf-dist/tex/latex/pgfplots/pgfplots.sty
$