Mencoder es un codificador de vídeo y audio muy potente que viene incluido con Mplayer, para pegar un subtitulo a un vídeo tenemos que hacer lo siguiente:

mencoder -ovc lavc -oac mp3lame pelicula.avi -o peliculafinal.avi -sub subtitulos.srt

Dependiendo del poder de procesamiento de nuestra CPU es lo que va a tardar en agregar los subtítulos a la película.