I found a setting in google maps where I can select the default media player. When using that media player, the bar will show up. The problem is, that for some reason only spotify is shown as a selectable app.
Screenshot taken on new device (Pixel 7 with GrapheneOS) with spotify selected as the media player:
https://imgur.com/a/FjOALjV
Edit:
Youtube Music is also available to select after I installed it. Based on this I'd guess this is more of android/google maps issue rather than to do with grapheneOS.
Unfortunately, I want that media control bar for apps like Symfonium and Audiobookshelf so that doesn't really help me :(