Haven't tried Fedora so far. But in Ubuntu and distributions based on it (like Mint, Xubuntu etc.) you get the choice to install them during setup.
You can choose them manually if looking for GStreamer ffmpeg video plugin and GStreamer extra plugins in the Ubuntu Software Center.
When it comes to Fedora. I've found a page here describing how to set up mp3 support on Fedora 16. Seems to work the same way for older versions. Including 14