I have a clean Ubuntu 15.10 installation these days. However, I noticed that video thumbnails (or previews) do not show up in Gnome Nautilus:

I prefer thumbnails to icons. Besides, I remember that Nautilus will generate a thumbnail for each video in Ubuntu 14.04. Thus, I took some time to look for the reason.

After trials and errors, I found gstreamer1.0-libav is the package in question. It is not installed by default. We can install it with:

$ sudo apt-get install gstreamer1.0-libav

In addition, we should clean the thumbnail cache; otherwise Nautilus won't regenerate thumbnails for videos. To clean the thumbnail cache:

$ rm -r ~/.cache/thumbnails/fail

Finally, refresh Nautilus with Ctrl-R. We should be able to see the thumbnails now:

If you still can't see thumbnails, it is possible that your videos are encoded by less popular codecs. Installing gstreamer1.0-plugins-ugly or gstreamer1.0-plugins-bad might help:

$ sudo apt-get install gstreamer1.0-plugins-ugly
$ sudo apt-get install gstreamer1.0-plugins-bad

However, please notice that gstreamer1.0-plugins-ugly might be covered by more restrict licenses or patents. And gstreamer1.0-plugins-bad might have worse quality, e.g. lack of code review, documentations, tests, and etc. Read GStreamer plug-ins splitup for more details.