Acoustic methods should work – after all, without air as medium the system wouldn't do much.
First order approach is a microphone that simply measures noise levels close to the fan in question.
That would entail rectification (possibly with a precision rectifier opamp configuration; might as well add a bit of gain while we're at it), and low-pass filtering (RC would do it), followed by some threshold (e.g. the Schmitt trigger input of a 74xx series logic IC, but honestly, a single transistor might just do; it's not that you're calibrating studio speakers, you're trying to figure out whether there's a fan running in front of your face).
Next better method probably is quite overkill, but: I assume there's some kind of enclosure. When I think of that I think "oh, an acoustic resonator!" and as a radio signals processing person, that brings a warm and fuzzy feeling of being at home. So, place a piezoelectric emitter and a microphone in that enclosure. Drive the emitter at fixed frequency (probably ultrasonic), and filter out that frequency in the receiver – that can happen in acoustic shapes (though I've never done this), analog forms (notch filter!) and digital forms.
Rotating blades cause Doppler effect. Given these fans probably spin relatively fast, significant Doppler effect, which you can observe as tones falling far enough from the emitter's frequency that they are outside of your filtering's stopband. Seeing that the frequency of these spinning rotor masses probably won't change too abruptly, this converts the question
How many fans are there in my system, and at which speeds are they running?
into one that's just
How many tones do I observe, and at which frequencies are these?
Without going into too much detail here, plenty of approaches to this spectrum estimation problem. The classical one being "just throw an FFT at it", but that limits your frequency resolution by the length of your FFT (not too bad, long FFTs are still extremely cheap). If you want to spend a few brain cycles on the problem, there's other nice models that fit here pretty well: estimating the parameters of an autoregressive model from Yule-Walker equations would be a beautiful thing.
(For perspective: Replace your ultrasonic transducer with a radio emitter. Now, some helicopter behind the next hill isn't directly visible, but it gets hit by indirect reflections off relatively stationary objects like other hills, buildings, parked cars…. Likewise, the reflections of the emissions hitting the helicopter blades are receivable at your position indirectly. Now, sometimes a helicopter blade will be moving in the direction the EM wave came from, causing a positive Doppler frequency, other times it will move away, causing negative Doppler. So, you would first receive these reflection, then estimate the frequency modulation around the transmit frequency, and then you'd estimate the frequency of the tone that will be in that – and you get the rotational speed of the rotor, times the number of blades. Because estimating frequencies (that you can know roughly a priori) can be done on long coherent sequences of samples with processing gain, the fact that you lose a lot of energy to free space and multiple reflections is not that much a problem.)
