ddg

Existen diferentes sistemas y programas (Avidemux, entre los mejores y al mismo tiempo fáciles: mini tutorial) pero me quedo con la línea de comandos y mencoder: ligero, rápido y seguro.
Sólo necesitas instalarlo, si es que aún no lo has hecho:
sudo apt-get install mencoder
y desde el terminal ejecutar esta instrucción (todo en una línea):
mencoder /ruta_a_tu_archivo.avi -sub /ruta_a_tu_archivo.srt -oac copy -ovc lavc -o /ruta_a_tu_nuevo.avi -subcp latin1 -font /usr/share/fonts/truetype/msttcorefonts/arial.ttf -subfont-text-scale 3.8
Por supuesto puedes cambiar la fuente, especificando la ruta (normalmente las tendrás en /usr/share/fonts) y el tamaño (en el ejemplo: 3.8, equivalente a unos 14 p)