Digital signal processing is not that easy. However, if you can find an FFT library you won't have to write the hard part of the code yourself.FFT/DFT
will give you the frequency components and their amplitude at any point/period of time.
If you have a pure tone or a pure square wave, you can simply measure the time between zero-crossings* (or between rising-edges) and calculate the frequency. (Real-world natural sounds contain more than one frequency so this may, or may not, work for finding the "fundamental" frequency.)
* Since the Arduino cannot accept the negative half of an audio/AC waveform, you have to add bias or otherwise deal with the negative signal, and then find the true zero-crossing or find a point near the zero crossing in software.