Question- how common are fully-remote software engineer gigs in Europe? I'm considering a relocation from the US (currently fully-remote) and this will be a huge factor in my decision.

This is much less. We say of the US that remote is "tradition" over there and it was used to explain why they can and we can't.

Covid changed things but they're is still a song mentality of in office work, especially in big older companies with an older middle management.