Where does Ubuntu store partition UUIDs on disk?
The UUID is stored in the superblock (of which there are many copies in case one gets damaged). The value itself is generated using libuuid, which is part of the e2fsprogs suite. There are many libraries for generating UUIDs; RFC4122 is a good place to start as it describes the more commonly used technique and includes reference code.
Here's a couple of links that may help - they are specific to ext2, but other variants should also have a similar place where they store the uuid:
http://www.nongnu.org/ext2-doc/ext2.html#S-UUID
http://linux.die.net/man/3/libuuid