Nyquist showed you have to sample at a rate at least twice the highest frequency you care about. This captures the information in your signal, but also causes artifacts from the frequencies above half the sample rate to show up in your sampled signal. These are called aliases. You therefore need to first eliminate the frequencies that will cause aliases, then sample.
Since no filter has a infinitely sharp cutoff, there will be some frequency range above the highest frequency you care about and below the frequency the anti-aliasing filter attenuates enough for you to get the signal to noise ratio you care about.
Analog filters are usually fairly gentle in their falloff. One approach is to apply a slow-falloff analog filter, sample at a high rate, then digitally filter that with a sharp filter to allow re-sampling at a lower rate. That last step is often called decimation.
For example, let's say you are after good quality voice and you're highest frequency of interest is 8 kHz. You might put a two-pole R-C filter on the signal with each pole at 12 kHz. You might sample the result at 100 kHz, which means anything past 50 kHz had better be attenuated below your noise floor. The analog filter will reduce 50 kHz by 25 dB, which you decide is good enough in this case since you know there will be very little content above 50 kHz to start with.
Theoretically you can take this 100 kHz sample stream and decimate it to 16 kHz, since that's twice the highest frequency you care about. Even a sharp filter, like convolving with a 1000 point sinc, needs some room to work with. Let's say 1/2 octave (that's really sharp), so the absolute minimum sample frequency after decimation would be 23 kHz (8 kHz plus 1/2 octave is 11.3 kHz, times 2 is 22.6 kHz).
You gave no spec on what kind of sound you want to sample, so you'll have to extrapolate to your requirements on your own.