To install the the video and audio codecs on Fedora 18:
1) Install the repositories provided by RPMfusion first.
rpm -ivh rpmfusion-free-release-18.noarch.rpm
rpm -ivh rpmfusion-nonfree-release-18.noarch.rpm
2) Now, install the plugins.
su -c 'yum -y install gstreamer-plugins-bad gstreamer-plugins-ugly gstreamer-ffmpeg vlc'
3) Restart the machine (not required but worked my case)
Note: The plugins are available at http://gstreamer.freedesktop.org/download/