According to Arch Wiki they get generated and stored in the partition when it is formatted. So kinda like labels but automated and with (virtually) no collision risk.

Uuids are part of the gpt (table) on the disk.

No. Since each partition gets its own UUID, it means it’s generated by the OS on creation, no matter the number of partitions. On boot kernel will scan all UUIDs and then mount and map according to them, which is sightly less efficient method than naming block device directly, but far easier for humans and allows you to throw your drives to whichever port you like.