How can a machine find a note's pitch just from its sound wave?

By comparing the sound wave with a delayed copy of itself. This technique, autocorrelation, measures the correlation of a signal with a shifted version of its own waveform, and it's a mathematical tool for finding repeating patterns or hidden periodicities hiding inside a signal, even one buried in noise.

A guitar tuner, a pitch-detection app, or the software behind Auto-Tune all face the same basic problem: estimate the pitch, or fundamental frequency, of a quasiperiodic signal like a plucked string or a sung note. The usual strategy is to find the signal's period, how long it takes the wave to repeat itself, and then flip that number upside down to get the frequency. Autocorrelation finds that period by sliding a copy of the wave against itself and checking, at each possible delay, how closely the two line up; when the delay matches the wave's true repeating period, the match is strongest. Algorithms with names like AMDF and ASMDF work this way, as do two of today's standard tools, the YIN algorithm and the MPM algorithm, both still built on autocorrelation.

For a long time it looked too expensive to run. Music engineers considered autocorrelation impractical because of the sheer amount of computation it needs, until Andy Hildebrand, building the pitch detector for Auto-Tune, realized most of that arithmetic was redundant and found a shortcut that, in his words, changed a million multiply-adds into just four.

It isn't flawless. These algorithms can be quite accurate on highly periodic signals, but they're prone to 'octave errors', mistaking a note for one an octave too high or low, they can struggle with noisy recordings, and in their simplest forms they get confused by polyphonic sounds, several notes playing at once with different pitches.

The same trick works at different timescales for different jobs. Applied to stretches shorter than a second, autocorrelation finds the pitch, which is how tuners and Auto-Tune work. Applied to stretches longer than a second, the exact same technique can pick out the beat of a song instead, which is how software estimates tempo. The method isn't limited to music, either: astronomers use autocorrelation to work out the frequency of pulsars.