The Subtitle Edit site has list of ways to add subtitles to video using...

To embed subtitles into...
mkv files (can be srt/ssa/ass or blu-ray sup or vobsub) use mkvtoolnix or Handbrake.
mp4 files use Handbrake or a Mp4Box GUI like Yamb.
avi files only - AutoGK or Total Video Converter.

Short description of how to add subtitle to video with these programs:
MKVToolNix 5.7
Handbrake 0.9.6
FFmpeg - Embedding or hardcoding (command line)
VirtualDub - Hardcoding of ssa/ass subtitles in video
Format Factory 2.96 - hardcoding of srt/ssa/ass/sub-idx in video (many output formats) files
Sony Vegas Pro - Embedding of srt subtitles