What size pot would I need?

Meh, 5 volts is enough

But how complex would a circuit be that controls the voltage for a given 3 wire fan?

If efficiency doesn't matter? A single NPN transistor on the fan's GND pin (on further examination, what Whitehawk posted is aimed at a PNP, being on the 12v supply side) a pot and a resistor should work. It won't be especially linear, but whatever. Here's a fairly old OCF article on this style: http://www.overclockers.com/small-and-simple-fan-voltage-regulator/
Bing made a rather nice one, the post is here: http://www.overclockers.com/forums/showpost.php?p=5270425&postcount=77

Efficiently? It's buck regulator time, which takes rather more doing.

The simple one is epic lol.

Simple, small and compact, I love tiny circuits like that
Thanks for the links Bobnova!

You betcha.
Putting a resistor on the BASE pin between it and the pot is a good idea, otherwise if you crank the pot down to zero ohms you're pretty much guaranteed to blow the hell out of the transistor.
You can look at the transistor datasheet and find the Max Base Current (it'll be called something like that) and size the resistor so that even with the pot at 0 ohms there won't be more current flow than the transistor base pin can handle.