TL;DR: I was driving my MOSFET gate at the supply voltage I was switching/ so I didn't maintain a high enough VGS. I'd failed to consider that Vs is not 0V once the MOSFET is on.
Per the accepted answer the simplest solution to that is putting the MOSFET on the low (ground) side so that VS ~= 0, making VGS easy to keep high. See corrected (but warning, still way too simplistic) circuit:
See tutorial article "MOSFET as a switch" and many others.
The immediate problem with the circuit in the question
The critical point is that the MOSFET's low resistance state Rds(on) is achieved when VGS is well above the gate threshold ... but not when VS is at 0V ground reference level. What matters is VGS when VS is at VD (with some handwaving for voltage drop across the MOSFET).
So if you are switching your supply voltage, your gate drive must be well above your supply voltage. That way your gate-to-output voltage is maintained and the MOSFET is kept in its low-resistance fully-on state.
The total charge required to switch the MOSFET from off to on is quite small and the gate current once it's fully on is tiny. So a variety of circuits can be used to boost VGS by increasing gate drive voltage above supply level. They don't waste much power because there's negligible current through them most of the time.
But you can't just drive the gate at the same voltage as the MOSFET's drain. It'll conduct because the VDS(drop) - the voltage drop across the drain-to-source path - maintains a nonzero VGS above the threshold voltage. But it won't get to the "on" VGS voltage needed to maintain efficient, low-resistance conduction.
I plan to add a schematic with a boosting gate driver of some kind soon. If anyone else has one, please share.
This great if in-depth article on MOSFET principles and applications shows some MOSFET gate-drive circuits.
If you're here you might find this article explaining MOSFET parameters useful too.
Making it work with a 3.3V input and PWM
A 3.3V input doesn't turn the gate on well enough to reliably reach RDS(on) on this MOSFET. Others are available that work at "logic level" gate signals. But you still don't want to drive them over a long wire from the microcontroller or PWM source.
This circuit will drive the MOSFET from a 3.3V input by using a low-side-switching NPN transistor for active pull-down and a resistor for passive pull-up. It's inverting, meaning the MOSFET is on when the 3.3V signal off and vice versa.
But .... relying on a resistor for pullup means it wastes power when on, as it produces a constant current. It also limits PWM speeds because the gate takes time to charge from the pull-up resistor and that means the MOSFET takes too long to turn on, wasting power (and producing heat) during its extended turn-on phase.
Really we want to actively drive the gate both down and up.
An active/active driver with discrete components
Here's my best effort so far, using a "totem pole" to switch 12V with a 3.3V input then a push/pull to drive the gate actively. It seems excessively complex though.