C'est bien mignon de faire style "Je suis sous Linux", mais bon finalement si on peut pas écouter sa musique ou se faire un petit DVD tranquillement et simplement, ça devient vite ennuyeux, et on commence presque a regretter nos fenêtres bleues... Donc autant y remédier de suite.
Je rappelle à toute fin utile que personnellement je suis utilisateur Debian...
La première chose à faire est de bien vérifier que vous avez vos dépôts correctement configurés (/etc/apt/sources.list): 
# multimedia
deb http://www.debian-multimedia.org etch main
Voici une liste non-exhaustive (qui sera certainement mise à jour) de paquets nécessaires ou utiles pour lire des fichiers vidéos ou audio sous Linux :
  • ffmpeg
  • libfaac0
  • libmp4v2-0
  • libswfdec0.3 (remplacé par libswfdec0.5-2 sous Debian Lenny)
  • libwavpack0 (remplacé par libwavpack1 à partir d’Ubuntu Feisty (merci Skankarius)
  • libxine-extracodecs (Ubuntu)
  • mimms
  • lame et lame-extras
  • faad
  • sox
  • mjpegtools
  • vorbis-tools
  • xvid4conf
  • libxvidcore4
  • libpng3
Ceux-ci fait ajouter aussi ces deux là ils peuvent etre bien utile :
  • w32codecs
  • libdvdcss2
Et enfin pour les utilisateurs de Gnome :
  • gstreamer0.10-ffmpeg
  • gstreamer0.10-fluendo-mp3
  • gstreamer0.10-gl
  • gstreamer0.10-pitfdll
  • gstreamer0.10-sdl
  • gstreamer0.10-plugins-ugly
  • gstreamer0.10-plugins-ugly-multiverse (Ubuntu)
  • gstreamer0.10-plugins-bad
  • gstreamer0.10-plugins-bad-multiverse (Ubuntu)
Voilà normalement avec tout ca vous avez de quoi faire. Pour ceux qui sont avides d'en avoir plus je vous renvoie vers le site : Linux on the root