Rhythmbox uses the GStreamer plugin system for media decoding. The plugins that are installed will determine which formats you will be able to play.

By default Fedora 23 includes the necessary plugins for decoding free formats. To search for the packages that support the media you want to play visit GStreamer.

A quick search on our Fedora 23 system reveals which plugins are pre-installed

rpm -qa | grep gstreamer

libnice-gstreamer1-0.1.13-2.fc23.x86_64
PackageKit-gstreamer-plugin-1.0.10-2.fc23.x86_64
gstreamer1-plugins-bad-free-1.6.1-2.fc23.x86_64
gstreamer1-1.6.1-1.fc23.x86_64
gstreamer1-plugins-base-1.6.1-1.fc23.x86_64
gstreamer1-plugins-good-1.6.1-1.fc23.x86_64

None of these provide MP3 playback. To enable this plugin you must first add the RPM Fusion repository.

To enable access to both the free and the nonfree repository use the one liner below

su -c 'dnf install http://download1.rpmfusion.org/free/fedora/rpmfusion-free-release-$(rpm -E %fedora).noarch.rpm http://download1.rpmfusion.org/nonfree/fedora/rpmfusion-nonfree-release-$(rpm -E %fedora).noarch.rpm'

On the GStreamer site we can see that in order to play MP3s we need the plug-in named gst-plugins-ugly. In Fedora this package is named gstreamer1-plugins-ugly.

sudo dnf install gstreamer1-plugins-ugly

For our convenience DNF automatically pulls in all the required dependencies.

a52dec, lame-libs, libmad, libmpeg2, opencore-amr, twolame-libs, x264-libs

Show the GStreamer packages after install

rpm -qa | grep gstreamer

libnice-gstreamer1-0.1.13-2.fc23.x86_64 
PackageKit-gstreamer-plugin-1.0.10-2.fc23.x86_64 
gstreamer1-plugins-bad-free-1.6.1-2.fc23.x86_64 
gstreamer1-1.6.1-1.fc23.x86_64 
gstreamer1-plugins-base-1.6.1-1.fc23.x86_64 
gstreamer1-plugins-good-1.6.1-1.fc23.x86_64 
gstreamer1-plugins-ugly-1.6.1-1.fc23.x86_64 

If for some reason you still receive an error when trying to play your media try deleting the following file

rm ~/.local/share/rhythmbox/rhythmdb.xml

Rhythmbox automatically recreates this file the next time a user attempts to play some media. Rhythmbox adds an entry type = ignore which appears to blacklist media when a codec is not available for playback. Deleting the file resolves the issue.

Audacious

One my preferred audio players. This one liner installs the program along with the plugin for MP3 playback.

sudo dnf install audacious audacious-plugins-freeworld

References:
https://wiki.gnome.org/Apps/Rhythmbox/FAQ
http://gstreamer.freedesktop.org/documentation
http://rpmfusion.org/Configuration