Programs to download subtitles for videos
You can use subdownloader or to install in shell sudo apt-get install subdownloader
which is very good to download subtitles for any type of movie/series.
After downloading/installing it the program should be in the Sound & Video section in the applications panel. If you are using Unity by default just press SUPER and type subdownloader and press enter.
When you open the program it will automatically log in to opensubtitles and just search for the movie you want to find the subtitles for or the folder where the video or videos that you want to search the subtitles for. Then select the language for them and download. It will automatically put it in the folder where the video is, renaming it to the video name and enjoy. Open the video with VLC and you should be able to watch the movie with the subtitles.
You can also try to install smplayer
which provides subtitle downloading natively.
You can go to 'Subtitles' --> 'Find subtitles on OpenSubtitles.org'
and get a list of all the available sub files.
The files are downloaded and saved instantly along with your movie file ;-)
Try subliminal, which downloads from multiple providers. It has all the features of other software suggested in this thread, but fares much better at detecting movie titles and finding quality subtitles.
You might need to run several passes on a given folder to find all subtitles, recursively.
It also detects embedded subs (mkv..), skips files which already have subs in your language of choice, and automatically renames the subs files to match video file names.
Also, I made a gist and an action, for the Nemo File Manager (can be converted to use Nautilus), that adds a context menu option to automatically download English movie subtitles.
It's available here on GitHub