How did XCode/OSX do that? Moved an XCode project to another location. XCode automatically knew where it was located

This functionality is available from pretty much every application's File » Open Recent menu provided by the convenience methods in LaunchServices/LSSharedFilesList.h (which is also the name of the plist files storing this information, e.g. ~/Library/Preferences/com.apple.Preview.LSSharedFilesList.plist).

These entries contain a serialized NSData (presumably), which you can copy and write to a file e.g. using a hex editor. They contain the full path to the file, the volume name the file is on, a UUID, and some additional information I currently cannot make sense if. I assume that the UUID is used to resolve the file reference if needed.

NSURLs can be converted to file references that can be resolved later, even when a file has moved. This answer on StackOverflow has more technical information.

I'm not sure, but HFS+ has inodes that uniquely identify a file. The NSURL functionality is possibly implemented on top of that. The observable behavior seems to indicate this: If you move a file to a different file system, it is removed from the Open Recent list of files, probably because it can no longer be resolved.

I don't know how XCode does that, but here's a generic answer.

In addition to paths, filesystem objects can have other identifiers, such as the inode number on Unix filesystemes or object ID on Windows NTFS, which can often be used to find all paths to a file with known ID. This identifier or number always remains the same as long as the object itself remains in the same filesystem, regardless of which directory you move it to.

Objects also have other, more visible but less reliable metadata such as the name, creation date, or size. If the object's ID is unknown or was not found anywhere, the program might search all filesystems for any object with the same name, type and size, or using other criteria. This is what Mac OS X Aliases and Windows Shortcuts do when their original target is missing (although shortcuts only work in the Windows shell, while aliases are more integrated with Mac OS).

It could be that XCode just uses the same functions used for resolving broken aliases.