How are they separate from other sounds? How is a 'beat' found in the audio?
It basically amounts to emphasizing the sudden impulses of sound in the song and then finding the fundamental period at which these impulses appear. This is done by breaking the signal into frequency bands, extracting the envelope of these frequency-banded signals, differentiating them to emphasize sudden changes in sound, and running the signals through a comb-filterbank and choosing the highest energy result as our tempo.
— Beat This - Beat Detection Algorithm
The first three steps should be easy to understand, let's look at the last step:
A comb filter adds a delayed version of a signal to itself, causing constructive and destructive interference. The frequency response of a comb filter consists of a series of regularly-spaced spikes, giving the appearance of a comb.
— Wikipedia - Comb filter
The last step uses such a comb filter to figure out the BPM, as you can see on this graph (145 BPM spike):
You also see a spike at 72,5 BPM, the inference pattern also creates spikes at the half and double frequencies. This is the reason that software sometimes picks the half or double BPM instead of the real BPM.
GameDev.net - Beat Detection Algorithms explains the whole thing in more depth.
How are tempo changes handled?
Most algorithms don't support tempo changes, they will either pick a part in the middle to determine the BPM or decide to calculate an average BPM as you suggested. From a DJ perspective I haven't seen an algorithm yet that supports mixing two songs with a dynamic BPM...
How would BPM calculation be different?
This doesn't depend on instrument or genre, but rather how it is played. For example, in an electro pop song the algorithm can easily be confused in a bridge part of the song or due to some kind of due to those overused digital effects. For the guitar, if you play a classic part with accurately timed notes it would be easy for the algorithm do determine the BPM you are playing.
