Eu usei Aegisub no Windows há alguns anos e fiquei muito feliz com isso. Aparentemente está disponível para Linux. É bem auto-explicativo.
Aegisub cria apenas o arquivo de legendas, por exemplo, um arquivo .srt. Para combinar o vídeo e a legenda para criar uma legenda codificada, você ainda precisa usar um segundo programa. No Windows eu usei o VirtualDub, mas ele não está disponível para Linux. Você pode encontrar um programa adequado na wikipedia .
Existem também outros editores de legendas
Atualização:
Não me lembro do Aegisub ter uma funcionalidade para definir automaticamente o início e o fim de uma frase falada no arquivo de legendas. E eu não vejo uma menção de tal função em nenhum lugar do site. No entanto, é muito fácil definir essas horas (combinações de teclas) manualmente.
Existe algum programa que possua tal função (em qualquer SO)?