Perso. je ne suis pas très rithmbox sinoon celui ci utilise gstreamer.
Tu trouveras ici une explication pour tout les principaux codecs
http://doc.fedora-fr.org/wiki/Lecture_de_fichiers_multimédia
En premier comprendre yum et le système de dépots
http://doc.fedora-fr.org/wiki/YUM_:_Configuration_du_gestionnaire_de_paquets puis activer le dépot livna.
Après dans une console taper simplement :
yum install gstreamer-ffmpeg gstreamer-plugins-ugly gstreamer-plugins-bad
Sinon si tu veux une interface graphique pour gérer (ou chercher) les paquets et les dépots, tu as smart qui est bon.