How do two UARTS know which baud rate to use?

Ordinary UARTs have to be pre-configured with the desired baud rate (as well as word length, stop bits, parity, etc) traditionally by a human.

For several decades now though there have been implementations of "auto baud" detection found in some settings, which typically works by timing key features of the waveform to deduce the baud rate. Early versions needed a known character to be transmitted, but more sophisticated versions might be able to find the rate from more arbitrary data.

A receiving UART typically has a local clock that runs at a faster rate - typically 8 or 16 times the baud rate. This is used to sample the incoming signal and detect the bits within a word in a way that can tolerate a few percent of error. Even two crystal oscillators wouldn't match rates perfectly, but the error tolerance can permit use of some less precise sources, sometimes including trimmed on-chip oscillators, etc. It can also help accommodate the fact that dividing down popular oscillator frequencies may only produce an inaccurate approximation to certain baud rates - in the old days, UART master clocks sometimes needed particular frequencies to access popular baud rates, for example 11.0592 MHz on the 8051 family.

Two UARTS "agree" on baud rate by means of documentation and by operator/user setting the baud rate by hands, including handshake protocol, stop bit size, etc.

Yea, everything is set up manually, which is often a bit of a pain, especially when systems are poorly documented (I'm looking at you, every embedded system ever).

I know USB, SATA, and most other modern data protocols start off after some reset or initialization event at the lowest speed with some standardized default configuration and negotiate with everyone else (or the just the master, depending on the protocol) up to higher speeds. Some also use pull-up or pull-down resistors on their data/power lines to indicate supported speeds.

See this website on USB negotiation if you're interested in delving a bit further in other protocols.