It does that with a completion script, typically put in /etc/bash.completion.d. All scripts in this directory are sourced by /etc/bashrc. Each app provides its own completion script.
The packaging system (RPM, deb) tracks files installed anywhere on the filesystem, including ones in /etc/bash.completion.d/, and will remove all of them when the application is uninstalled. "Symlink magic", whatever that is, won't help at all.
I know that the package manager keeps track of it. I did not express myself clear enough.
> The packaging system (RPM, deb) tracks files installed anywhere on the filesystem, including ones in /etc/bash.completion.d/, and will remove all of them when the application is uninstalled. "Symlink magic", whatever that is, won't help at all.
If all the files needed for a package / program are in one place, the job of the package manager gets easier.
You might want to have a look at GoboLinux. They are trying to make the file system the package manager. (Haven't used it, yet, though. Still using a Linux with a traditional package manager.)