Extension:TimedMediaHandler#Minimal_install_under_Ubuntu_12.04 doesn't sound very good, those repositories have not been updated since 2011; also, it conflicts with advice above which says to use a firefogg repository. How about libav, ibvpx?
Topic on Extension talk:TimedMediaHandler
I've also filed phab:T86477 for further simplification. In the meanwhile I checked the readme and the following commands were enough for me to embed a WebM video from Commons (might be different when not using apt.wikimedia.org though):
apt-get libav-tools oggvideotools ffmpeg2theora
nano LocalSettings.php # Enable mwEmbedSupport, TimedMediaHandler, InstantCommons
php maintenance/update.php
php maintenance/rebuildLocalisationCache.php # Update magic words to avoid exceptions, if using l10n cache