The issue lies in what happens to the power. Drew is more or less right about the ratios, and resistance of the pot & armature resistance of the fan.
Here's the situation: we have a fan, that runs of voltage V1 (I assume it's a computer fan --> V1 = 12V). We want to control the speed of this fan. To do this, we must change the voltage drop across the fan. There are two main ways to do this:
1. Change the total resistance of the circuit. We do this by putting a variable resistor (potentiometer, rheostat, etc) in series with the fan. What this does is introduce a second voltage drop in the circuit (V2). This limits the voltage available for the fan (V1 = 12 - V2). This is simple enough, but has a few drawbacks. Mainly, that this second voltage drop (V2) is dissipating power. How does it do this? Heat. Wasted energy. Plus, the component needs to be able to withstand that heat (25R pot dropping 6V needs to dissipate nearly 1.5W of heat...)
2. Change the voltage running to the fan. There are a few ways to do this (variable voltage regulator, DC-DC converter, PWM...) all with pros and cons. Pretty much, PWM is our best bet here. Basically, we run the fan at full voltage, but turn it on and off quickly enough, that the fan pretty much sees an "average" voltage across it. By changing the proportion of on-time to off-time (duty cycle), we control what that "average" voltage is. The benefit of this (particularly when combined with mosfet drive, as my circuit does) is that when the fan is on, it's on, when it's off, its off. The amount of energy drawn by the circuit is roughly proportional to the duty cycle. There is negligible component heating, so virtually no wasted (heat) energy. And you get the whole voltage control range (0-12V) without having to worry too much about pot value (or power rating).
If I've lost you (or me) above, basically: PWM is the best. You'll get better control, more efficient operation, better component life and lower component cost. That ebay linked controller looks good enough. Or if you prefer to build it yourself, the one I linked before is a good option (the one I designed and made), but there are plenty of others out there if you want to look around. I had most of my components already, so it didn't even cost the $7 or so I listed for components...