Gunshots have no specific frequency, it is "noise", i.e. many different unrelated (not harmonic) frequencies. So FFT etc. is likely to be difficult.
Detecting a gunshot with a microphone will be easy (threshold)
You could try recognising different types of shots by "correlating" some series of ADC captures, assuming that the distance
mike-gun won't screw everything by saturating the microphone...
In any case, an Arduino can't usually run at speeds high enough for simple audio processing. For example, it can't even play MP3.
Go for a fast 32-bit at least (PIC or ARM)