Existem várias maneiras de criar o TOC em PDF. O melhor é provavelmente usar o arquivo pdfmarks, que expõe todas as possibilidades descritas pela Adobe pdfmarkReference
Não é tão difícil de analisar programaticamente documentos PDF e coletar informações necessárias para criar esses arquivos pdfmarks, que posteriormente podem ser incorporados em arquivos PDF usando o GhostScript, por exemplo.
Para uma maneira fácil de adicionar manualmente entradas de sumário, como você deseja, o utilitário GUI do PDFMod pode ajudar. Está listado no Synaptic