As far as I understood, you are trying to make some kind of a sound level detector, which will let you detect if there is a sound with a certain volume or not. You can do this with minor changes to the schematic you have. But before that, you should understand the circuit.
Let's break that circuit down. First of all the part with the microphone.
R1 is for supplying power that is needed by the microphone and this is called biasing the microphone. A microphone generates an AC voltage, which is sometimes negative and sometimes positive and it changes most of the time. Think of a sine wave. But remember, we had some biasing to it which is a DC voltage. We have to take that out and give only the AC voltage to the amplifier. And doing this is easy with a simple, single capacitor. A capacitor does not let the DC to pass, but lets AC pass easily. We have blocked the DC portion of the voltage on the electret microphone.
Now, let's look at the amplifier itself. Imagine that there is nothing else but the below schematic:
In this configuration, the transistor is biased to be in the linear region. It is in the edge of being turned ON or turned OFF, but it is neither of it. If it was fully ON, it would be saturated. If it was fully OFF, it would be not conducting at all. But it is in the middle, which is called the linear region.
When it is configured like that, if you touch (not literally) to the base of it, creating a small change, the output will be changing largely. This is what amplification called. You can beg Google for more detailed information.
What if we combine the two circuits mentioned above. A biased electret microphone with a capacitor will output small changes with respect to sound. The transistor will amplify these small changes so they can be viewed easily:
Notice that I have changed C1 to 1uF. You can use values up to 100uF. You will probably need electrolytic capacitors. Also, notice that there is no more an output capacitor. This means that you will have an output voltage somewhere between 0 and 5 V, depending on the sound level. If you have an oscilloscope, view the waveform on the output. If you do not, try lighting an LED if the analog read is higher than, for example, 750. Experiment with different values than 750, then report me the results.
Your sample rate must be twice the maximum frequency of interest. This is the Nyquist–Shannon sampling theorem. If you want hi-fidelity audio, your maximum frequency is the limit of human hearing, about 20kHz. Human voice is less demanding: telephone networks work up to about 3400 Hz.
You will find that the AVR's ADC isn't terribly fast, and you don't have much resources to process the data. So probably, your hardware limitations will dictate the sample rate for you.
You probably don't need to worry about codecs. A codec encodes and decodes an audio stream. A common thing to do is compress the audio for more efficient storage or transmission, but it doesn't sound like you are doing either. There are codecs that encode and decode for reasons other than compression, but I can't think of any that would be relevant here. Your computing resources are very limited on the microcontroller anyway, and you won't have much time for encoding or decoding anyway.
Best Answer
You are running a gain of 40 dB. Any noise that is present at the input will be amplified by 100x.
There are several possible places where the noise might enter the circuit but the most likely spot is the bias resistor. There are a couple of things that you can try.
1) Move the bias resistor power lead from Vcc to ground. Although the mic won't work, does the noise go away?
If it does, you need to add a low-pass power supply filter to the bias supply. This can be as simple as another 10k resistor in series with Vcc and a large capacitor from the junction of the two resistors to ground.
2) Disconnect the mic. Does the noise go away? If so, try a different mic capsule.
One very rare problem that I've had in the past is that the ground trace that connects to mic's the metal case was broken. This allowed the metal case to pick up nearby noise spikes. Replacing the capsule fixed the problem.