I would assume that the solenoid is ground referenced so that you need a high side driver. i would also assume that the 5V pwm signal is coming from a microcontroller and you don't want much current pulled out of it.
how about tying the 5V pwm signal to the gate of a peanut NFET, say a 2N7000. The source is tied to common/ground and the drain is tied to a 10k resistor whose other end is tied to 12V. Maybe have a 10k resistor across the gate-source to make sure it is off if the cpu is not awake but 12V is. Connect the gate of a PFET (don't know a good one off hand - i don't use them too much - but it needs to handle current - may need a heatsink as well) to the drain of the NFET, the source to 12V and the drain to the solenoid.