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