Está no pacote gpac
.
Clique no botão vermelho para instalá-lo facilmente com o Ubuntu Software Center:
Ou instale-o com o terminal:
sudo apt-get update
sudo apt-get install gpac
(Obrigado ao @ uri-herrera!)
Eu usei o MP4Box no passado para permitir insinuar em arquivos mp4 no passado, mas parece que não está mais nos repositórios. Existe mais alguma coisa que possa ser usada ou eu preciso compilar da fonte?