I have tried several suggested methods and commands, mostly using mencoder with commands like this:
sudo mencoder movie.avi \
-ovc lavc -oac mp3lame \
-sub movie.srt \
-font "/usr/share/fonts/truetype/msttcorefonts/tahoma.ttf" -subfont-autoscale 2 \
-o movieplussub.avi
The problem is that the subtitle is in non-Latin fonts (but still utf8) however they end up being displayed on the avi as '???????' .