I don’t think you can just fit the new drive and set it up from recovery, it’ll never see the drive to use it.
Actually, yes you can. I installed the blank, unformatted new SSD. The only "problem" was that entering the recovery mode using Command+R would not download the latest version of macOS. When I did that, I ended up with a "OS X" labelled version. So no support for NVMe since that came with macOS Sierra.
What I actually needed to do was entering the recovery mode with Option-⌘-R. This way, the latest compatible macOS version is downloaded. And that one actually did support NVMe and I was able to see the drive and format it.
Thanks to user @Birkan for that.
The support document on Option-⌘-R states that starting recovery mode with Command+R is downloading the macOS version that was last installed on the computer. Since I started with a blank SSD installed there was no way for it to determine which macOS was "last installed". So I guess it just downloaded the one that was installed when the computer shipped back in 2015. And that was some version of OS X (before the rebranding to macOS).
On a different note:
I unfortunately did not format my "old" SSD before replacing it with a new one.
So I would have to reinstall it to safely format it so I can sell it.
Or I get an external enclosure with a USB port. But it looks like those are only available for around $50 and upwards for my MacBook Pro 2015. For the Macbook air 2012 model they seem to be cheaper, starting at $15.