Alors un petit résumé...
Gstreamer est un framework multimedia servant de base pour la lecture/enregistrement de videos et audios dans moultes programmes... Pour le moment se sont principalement des programmes fais pour Gnome. Mais Gstreamer est indépendant, et KDE va également le supporter. C'est en fait un moteur, au même titre que Xine.
Gstreamer, et donc toutes les applications basées dessus, peuvent donc lire et enregistrer des medias dans différents conteneurs (mkv, avi, ogg, mp4...) et utiliser les codecs disponibles pour décoder/coder leurs contenus video et/ou audio.
Ce qui fait la force (entre autre...) de Gstreamer c'est qu'il est modulaire et fonctionne avec des plugins pour avoir de nouvelles possibilités, principalement nouveaux codecs.
Ces plugins sont classés dans plusieurs catégories :
- base : les codecs de base, ne posant aucun problème légaux, de très bonne qualité (ogg, theora...)
- good : comme les bases, mais avec des codecs moins répendus pour le commun des utilisateurs lambda (flac, dv, speex...)
- bad : codecs généralement encore en phase de développement, non finalisés, ou manque de documentation, mais quand même fonctionnels (faut pas pousser non plus

) (mpc, swf...)
- ugly : les codecs plus ou moins litigieux légalement selon les pays (mp3, dvd...)
Les variantes multiverses rajoutent encore des codecs, jugés "limites" pour le moment (aac, xvid...). Mais tout ceci est complètement utilisable, en particulier pour la lecture de videos et audios.
Donc si tu utilises Totem-Gstreamer (par defaut sous Ubuntu), je te conseille d'installer tous les "gstreamer0.10-plugin..." base/good/bad/mad-multiverse/ugly/ugly-multiverse , également "gstreamer0.10-ffmpeg" , et "gstreamer0.10-pitfdll". Ce dernier se sert des w32codecs pour les formats proprios (wmv, rm...).
Quant aux "fameux" w32codecs, ils servent si tu utilises le moteur Xine (Totem-xine, gxine, Xine-ui...). C'est donc un autre moteur, plus ancien, plus complet sur certains points (très rare maintenant), mais moins évolutif. Perso j'ai en plus de Totem installé Gxine, au cas où... (si tu veux lire certains codecs avec, il te faut aussi installer le paquet "libxine-extracodecs")
Ces w32codecs servent aussi avec mplayer. C'est vraiment le couple qui te permet de tout lire. Par exemple, c'est chez moi la seule façon de lire des video rv10 (Real) dans un mkv. Bien qu'en théorie totem-gstreamer (avec pitfdll) et xine doivent pouvoir le faire, ils n'y arrivent pas... de plus si tu rajoutes "mozilla-mplayer-plugin", tu pourras lire toutes les videos du net... (ou presque)
Et tu as aussi VLC qui fait de plus en plus de miracles
Donc pour résumer, tu as principalement totem-gstreamer avec tous ses plugins qui suffisent dans 99% des cas.
Sinon tu as le couple w32codecs/Mplayer pour le reste.
Et tu as aussi Xine et VLC au cas très improbable que les 2 méthodes précédentes échouent.
Quand tout le reste a échoué, lisez le mode d'emploi.