It might be helpful to add some info to narrow the possible solutions. The power (how much current at 12 volts) demand is important - a computer fan, if large enough, can draw more power than some small batteries can supply.
Do you want the batteries to be rechargeable? If I am not mistaken, one pound of alkaline batteries will supply the fan for more time than one pound of rechargeable alternatives, all other things being equal. Among rechargeable options are ni-cad, ni-mh, gel-cell (lead-acid or other). The cost, capacity, size, etc all factor into the selection.
If you cannot purchase a single 12 volt battery (the old lantern batteries come to mind) then you can string together 2- 6 volt batteries, 4- 3 volt batteries, 9 - 1.5 volt cells or 10- 1.25 volt cells. AAA will supply the least current - D cells the most. If the battery can't supply the current the fan won't run at all - or for very long.
"As long as possible" is a loose description so it might help to know how long is enough. At a high level if you know how much power the fan needs - you can compare it to the power that a given battery will deliver as a way of zeroing in on where you are at.
It is certainly possible to work the answers out - this is engineering and design. That could be a lot of work. An alternative is to experiment. Get some AA batteries together - 9 alkalines - tape or otherwise fasten them together in series - attach the fan and see if it runs at all and if it does, for how long does it do what you want it to do. If the time is too short then move up to C or D cells. Just use what you might have on hand - it's a place to start.
It is possible, at low cost, to convert the 3 volts you might get from a pair of AAA, AA, C or D cells to 12 volts with a up-convertor switching regulator. See National Semiconductor website - lots of good design info. You'll need to understand how much current the fan needs and how much current the battery of choice can deliver. The power input will need to be greater to account for the inefficiency of the conversion.