[nathan_phoenix]

Same way as how Signal desktop works with the phone being turned off.

As another commenter noted, they just generate another key and when someone sends you a message they have to encrypt the same message twice (one for each key).

[Aachen]

Signal exchanges keys in the QR code. It's not that you generate a random new key and people just start encrypting for that key without verification.

(I don't use WhatsApp so I don't know if they do the same.)