The idea of autocorrelation is to provide a measure of similarity between a signal and itself at a given lag. There are several ways to approach it, but for the purposes of pitch/tempo detection, you can think of it as a search procedure. In other words, you step through the signal sample-by-sample and perform a correlation between your reference window and the lagged window.
The correlation at "lag 0" will be the global maximum because you're comparing the reference to a verbatim copy of itself. As you step forward, the correlation will necessarily decrease, but in the case of a periodic signal, at some point it will begin to increase again, then reach a local maximum. The distance between "lag 0" and that first peak gives you an estimate of your pitch/tempo.
The way I'm going to describe how to compute it in practice yields something slightly different (i.e. cyclic vs. acyclic mostly), but that's the conceptual basis for how it works.
Computing sample-by-sample correlations can be very computationally expensive at high sample rates, so typically an FFT-based approach is used. Taking the FFT of the segment of interest, multiplying it by its complex conjugate, then taking the inverse FFT will give you the cyclic autocorrelation. In code (using numpy):
freqs = numpy.fft.rfft(signal)
autocorr = numpy.fft.irfft(freqs * numpy.conj(freqs))
The effect will be to decrease the amount of noise in the signal (which is uncorrelated with itself) relative to the periodic components (which are similar to themselves by definition). Repeating the autocorrelation (i.e. conjugate multiplication) before taking the inverse transform will reduce the noise even more. Consider the example of a sine wave mixed with white noise. The following plot shows a 440hz sine wave, the same sine wave "corrupted" by noise, the cyclic autocorrelation of the noisy wave, and the double cyclic autocorrelation:
Note how the first peak of both autocorrelation signals is located exactly at end of the first cycle of the original signal. That's the peak you're looking for in order to determine the periodicity (pitch in this case). The first autocorrelation signal is still a little "wiggly", so in order to do peak detection, some kind of smoothing would be required. Autocorrelating twice in the frequency domain accomplishes the same thing (and is relatively fast). Note that by "wiggly", I mean how the signal looks when zoomed way in, not the dip that occurs in the center of the plot. The second half of the cyclic autcorrelation will always be the mirror image of the first half, so that kind of "dip" is typical. Just to be clear about the algorithm, here's what the code would look like:
freqs = numpy.fft.rfft(signal)
auto1 = freqs * numpy.conj(freqs)
auto2 = auto1 * numpy.conj(auto1)
result = numpy.fft.irfft(auto2)
Whether you would need to do more than one autocorrelation depends on how much noise is in the signal.
Of course, there are many subtle variations on this idea, and I'm not going to get into all of them here. The most comprehensive coverage I've seen (in the context of pitch detection) is in Digital Processing of Speech Signals by Rabiner and Schafer.
Now, as to whether autocorrelation will be sufficient for tempo detection. The answer is yes and no. You can get some tempo information (depending on the source signal), but it may be hard to make sense of what it means in all cases. For example, here's a plot of two loops of a breakbeat, followed by a plot of the cyclic autocorrelation of the entire sequence:
For reference, here's the corresponding audio:
http://soundcloud.com/datageist/breakbeat-autocorrelation
Sure enough, there's a nice spike right in the middle corresponding to the loop point, but it came from processing quite a long segment. On top of that, if it wasn't an exact copy (e.g. if there were instrumentation with it), that spike wouldn't be as clean. Autocorrelation will definitely be useful in tempo detection, but it probably won't be sufficient by itself for complex source material. For example, even if you find a spike, how do you know whether it's a full measure, or quarter note, a half note, or something else? In this case it's clear enough that it's a full measure, but that won't always be the case. I'd suggest playing around with using AC on simpler signals until the inner workings become clear, then asking another question about tempo detection in general (as it's a "bigger" subject).