Вообще, тема поддержки кодирования-декодирования аудио и видео весьма широка. Зачастую сложно найти и под Windows нужный кодек, если автор записи был оригиналом. А ведь считается, что Windows в этом плане поддерживается лучше.
Поэтому сразу оговорюсь, что данное решение подходит для 99% случаев (это не преувеличение).
Итак, в стандартной поставке Ubuntu (на диске) многих кодеков нет. Всё из-за их закрытости. Однако, при установке предлагается их скачать.

Предположим, вы не скачали их при установке Ubuntu. Когда-то давно можно было скачивать их по ходу работы: приложения в Ubuntu жаловались на то, что не могут распознать формат, и пытались выкачать кодеки для поддержки его. Но теперь всё несколько иначе.

Специально, чтобы можно было скачать одним махом все распространенные, но закрытые кодеки, сделали пакет ubuntu-restricted-extras. У него в зависимостях указаны все нужные пакеты. Кстати, Flash плагин от Adobe тоже там есть.
Итак, чтобы решить большинство проблем с кодеками, нам нужно всего лишь установить специальный пакет.
В консоли:
sudo apt-get install ubuntu-restricted-extras
