Actually not much magic. You asked a few different questions, so I will try to give you every answer:
How are UTI created for each file?
Launch Services maintains a database of all applications (and some other types of packages) on your Mac and the corresponding information declared in their Info.plist files. It automatically updates this information - I think it has a daemon that monitors the file system to keep track of changes in applications, but I donβt know the details. I know that you can request a tool called lsregister to upload the entire database for you. In the terminal on a mountain lion:
$ /System/Library/Frameworks/CoreServices.framework/Versions/A/Frameworks/LaunchServices.framework/Versions/A/Support/lsregister -dump
Various UTType functions also gain access to this database of startup services (although I'm not sure if they do it directly or if they communicate with some kind of daemon that does this for them).
Where are UTIs stored at the file system level?
Well, the actual Launch Services database seems to be located somewhere differently on every Mac. In my opinion, this is similar to /private/var/folders/mf/1xd7vlw90dj5p4z1r5f800bc000101/C/com.apple.LaunchServices-0371025.csstore . (At least lsregister keeps this file open at run time, I'm not really sure what it is, but I assume it is a database.)
This is just a list of declared UTIs. There is no UTI field attached to this file. When you ask Cocoa for a UTI-through file, say -[NSWorkspace typeOfFile:error:] or -[NSURL getResourceValue:forKey:error:] , it actually extracts the path extension from the file name and then calls UTTypeCreatePreferredIdentifierForTag() to retrieve the corresponding UTI. (This is a bit more complicated because it also considers things like the path leading to a device directory or file or something like that, but this is the main idea.)
Does this mean that UTI is stored along with Spotlight metadata? What to do if Spotlight is turned off?
Spotlight stores UTI files in its database, but it allows you to quickly search and filter by type. Like everything else in the Spotlight index, this information is not canonical; it is simply used to quickly search for data that is actually stored elsewhere. If you turn off Spotlight, it does not depend on him.
Is it correct that the API cannot manually add or change the UTI for a specific file?
Yes, because UTI is computed at runtime from other file information. Changing the UTI file has the same meaning as changing the length of its name - you cannot do this without changing the name itself.