LinuxParty

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:

(Ubuntu): sudo apt-get install mencoder
(Fedora): yum install mencoder

Lo primero, crearemos nuestro fichero .srt, un ejemplo de su contenido:

Ejemplo de código de subtítulo en SubRip de la película la Roca

1
00:07:37,927 --> 00:07:40,487
LABORATORIOS DEL FBI
WASHINGTON, D.C.

2
00:28:39,487 --> 00:28:42,445
MUELLE 39 - CENTRO DE MANDO MOVIL DEL FBI

3
00:56:56,326 --> 00:56:58,556
15 HORAS DE PLAZO

4
01:30:40,966 --> 01:30:43,844
8 HORAS DE PLAZO

5
01:35:48,966 --> 01:35:52,163
52 MINUTOS DE PLAZO

6
02:05:31,086 --> 02:05:35,716
ESTA PELÍCULA ESTA DEDICADA
AL RECUERDO DE DON SIMPSON

Ejecutamos desde la línea de comandos...

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)