How to combat noise from my circuit polluting my 12V rail?
The 1000uF capacitors C1 and C3 might not be able to handle such high frequency switching transients very well. Large value caps always have very bad high frequency response.
I suggest trying to replace the 1000uF with low ESR capacitors of 47 - 220 uF and see how that goes. Maybe also place a ceramic capacitor (100 nF - 470 nF) in parallel with both.
I also suggest watching this video form Dave's EEVBlog about bypass caps, although not exactly your situation, the non-idealities of capacitors that are explained in this video also apply to your problem.
You might try increasing the value of R2. This will decrease the dV/dT on the gate and slow the edges when the mosfet switches. 10 ohms is usually a good place to start, but you may have to experiment.
Adding to the other answers after your PCB layout update:
Without a ground plane to create a low inductance ground, every track labeled "GND" will have quite high inductance, about 7nH/cm for a 1mm wide track.
Thus the caps are inefficient at filtering HF, because little inductors (also known as traces) are in series with the caps, increasing their HF impedance. A SMD ceramic cap has a much lower inductance than an electrolytic, not due to magic but simply because it is smaller, so it will be better at HF decoupling... however the inductance of the traces is still in series.
Additionally, since you have fast di/dt currents in your GND, the potential along the GND traces will vary all over the place. Remember:
e=L di/dt
di = 100mA, dt = 20ns (fast switching FET), L=6nH per cm, thus e= about 50mV per 10nH of trace inductance... not exactly "low-noise".
...thus on such a PCB without a ground plane, when fats high currents are involved, it is usually impossible to measure anything, because the signal shape will change a lot depending on where you probe the ground.
As you noticed, the solution is not to have any HF and high di/dt currents in yoru circuit to begin with, and this is achieved by slowing down the FET switching with a resistor.
If your PWM is slow enough (say, 30 kHz) switching losses will be very small anyway.
This has the extra benefit of not sending high di/dt pulses into the fan wires, which prevents them from acting as antennas and radiating noise all over the place, which would be an excellent way to build a wideband radio jammer...
Don't even think L3 and C5 will do anything: the self-resonant frequency of these inductors is usually quite low (check the datasheet) which means at the noise frequencies of interest, they are capacitors. Also your 100µF output cap is an inductor. And all the traces are inductors, especially the ground, which means the voltage on output "GND" is not 0V, but will have some HF noise too, this will also add some HF common mode noise on your wires.
Likewise, if you multiplex LEDs or scan a matrix keyboard, don't use a driver with 5ns edges! These are basically huge antennas. A square signal with 5-10ns rise time will have nasty harmonics way above 1-10 MHz no matter the switching frequency.
So... unless you want that extra % in efficiency, always switch as slow as you can get away with! It's a good rule of thumb to avoid EMI problems.