You could get a big sealed lead acid battery, like those optima batteries. It wouldn't be very portable, but the battery life would be kick ass.
Seriosly though, just get any combination of batteries that adds up to 12 volts, then hook the red wire from the fan up to the + side of the battery, and the black wire to the - side. You could probably use a 9 volt battery, the fan wouldn't spin as fast, but it would work. There's also 12 volt lantern batteries. Or 8 AA batteries, that's 1.5v times 8 which equals 12 volts.