O UUID é armazenado no superbloco (do qual há muitas cópias caso alguém seja danificado). O valor em si é gerado usando o libuuid, que faz parte do pacote e2fsprogs. Existem muitas bibliotecas para gerar UUIDs; O RFC4122 é um bom lugar para começar, pois descreve a técnica mais usada e inclui o código de referência.
Aqui estão alguns links que podem ajudar - eles são específicos do ext2, mas outras variantes também devem ter um local semelhante onde eles armazenam o uuid: