The first thing I noticed was that it actually worked out of the box, and after installing gstreamer-ffmpeg all of the codecs I needed were working!
Unfortunately, the second thing I noticed, was that as soon as I started a video that sets the Flash volume to 100% (for example YouTube does this), my system volume also suddenly jumped to 100%, setting my headphones to deafening levels.
After some searching on the web, I discovered that this is caused by a PulseAudio feature called "Flat Volumes".
This feature was meant to enable specific applications (for example a VoIP client) to turn up its volume, and Pulse Audio would
accomodate the system volume while decreasing the volume for other applications so they'd stay on the same volume.
While this is a pretty neat feature, I think that the Pulse Audio developers should either not have enabled it by default (which
it is), or made it so that application developers explicitly have to request it (note: I don't know too much about the sound stack,
but if an application triggers this without their intention, I think it might be up for improvement).
It is pretty easy to disable this feature: just create a file ~/.config/pulse/daemon.conf with a line "flat-volumes = no".
After this, restart pulseaudio by running pulseaudio --kill && pulseaudio --start .
After this fix, the volume works as expected.