What is drive voltage?
There is no current or power limiting here, you may well have had it fail due to inrush. Maybe the fan has a bypass capacitor inside? Dumb enough to happen...
In a "dumb switch that just works" application, it's probably worthwhile to use a MOSFET that's overly large, large enough that you can ensure it will cause the fuse to open (like a self-resetting polyfuse). You can also gain some leverage if the drain and fuse are thermally coupled (polyfuse is just a PTC with a sharp curve at 120C or so), though this may not be fast enough to prevent damage (if the fuse is heated to 120C, how much did the transistor's junction temperature heat up, above that?).
And to determine those ratings, sum up Rds(on), fuse resistance (minimum), fan resistance (if you can estimate it -- best guess at the minimum, just the wire resistance??) and power supply resistance (because if your supply is weak, you may well end up browning it out, too), and figure you need to withstand whatever short circuit current flows through that resistance. Obviously the Rds(on) term depends on selection, but you can use the peak power theorem to see how to limit that. Example: if everything else is 0.1 ohm, then a 12V supply will be capable of 120A peak and 1440W peak. You might want to limit that to 14W peak in a beefy device (DPAK?), making some assumptions on how fast it will happen (a DPAK will take 14W or more for, probably tens of miliseconds, but only a watt or two continuous without extra heatsinking), which would require a 0.001 ohm transistor. Well, that's quite unreasonable, so nevermind that, I guess. But it goes to show how strenuous fault conditions are, if you try to get semiconductors involved.
Tim