Their iCloud security page says “Safari History, Tab Groups, and iCloud Tabs” is end-to-end encrypted. So they store history to sync across devices but the keys are only on your devices.
Are the "keys" just your iCloud password (or a deterministic derivative thereof)? Otherwise, how could your tabs magically appear on a new device?
The keys are encrypted with your device pass codes. Setting up a new device requires the pass code from another device.
Nope, they are not your iCloud password. Keys for E2E items are kept on device and then there’s a process to join a signing circle for syncing. What this means in practice is to sync you need to allow your new device to be accepted into the circle from an existing device.