Okay, now that I had a little time I took a closer look at this and indeed, Nautilus just follows the Dark/Light theme preference set in gnome-control-center. While it might not use libadwaita yet, it clearly follows this preference already. Seems like themes ending in "-Dark", with capital D, work automagically though. Materia, unfortunately, has the small D (strongly resisting the urge to make a joke here).
The headerbar sometimes won't change with the theme because there still is some nautilus process running in the background, which apparently blocks the theme update (best guess). After a killall nautilus and starting it again, it always changes to the correct theme for me. Sometimes the same issue happens for themes ending in "-Dark" and you have to completely kill and relaunch nautilus for it to apply the dark preference + headerbar.
So yeah, if you have a dark theme ending in anything other than "-Dark" (even if it's only a lower-case "d"), you're going to have to launch gnome-control-center, go to the Appearance section and select the "Dark" preference (and vice versa). Otherwise it will just stay bright.
