I had this problem, but after not being able to resolve it I tried Bazzite and found the gaming experience was much better there anyway, so switched. This problem doesn't exist on that distro.
The Fedora documentation has the answer: Installing plugins for playing movies and music
Fedora (combined with RHEL) has great documentation, take an hour, read the docs and you'll have a great experience.
I just installed fedora a couple of days ago and this happens to me too...
I guess I'll try a different distro 🤷♂️ it was being a nice experience until I tried to play a video
I mean yes, it's a way to solve playing offline videos, but it doesn't seem to stop there. I found that codecs for playing videos on Firefox are also missing
I could install Chrome as well or hack my way, but it makes me want to recommend the distro to beginners even less
