Voltage Regulator - I'm drawing a blank...

I have a 12v input and, using the Arduino, I need a controllable voltage output between ~3v and the full 12v... Any ideas?

It's not too clear what you want. If you want a voltage regulator then you won't find any linear regulators that take 12V in and put 12V out.
But you might just want a signal line that goes from 3V3 to 12V, in that case a transistor, filter and using PWM will do it for you.

But you might just want a signal line that goes from 3V3 to 12V, in that case a transistor, filter and using PWM will do it for you.

That sounds about right. Could you draw up a diagram for it?

Well you can filter before you up the voltage or filter after.
This shows the filtering before as it has the advantage is being able to use bigger resistors and smaller capacitors:-
Imgur
You can replace the FET with a transistor if you like, otherwise you can use any sort of N-channel FET, not just the one shown. Where it says FAN that is where you want to place your load. The two points shown as 12V can be connected together.