Many package managers in Linux distributions and BSD flavors track package dependencies. But before a package goes into a repository, it is investigated by a maintainer, who tracks the dependencies manually.
What software can be used to track package dependencies? Plain text files are not very good, because they are flat. Outliners that can keep data structured in trees are better, but not ideal, since dependencies do not always form a tree, sometimes they form a graph.
Please bear in mind that I'm not looking for something that can resolve dependencies automatically. I'm looking for an app that could store the dependencies between packages and allows queries to display the dependences for packages (like package managers).
Not sure I understand your question, but that is just what package managers do.
On Debian e.g. you can use
to show packageX's dependencies, and
to show reverse dependencies (packages that rely on packageX).
If that's not what you are looking for, maybe you could describe what you want to do?
I'm not that experienced with repository/package maintenance, but I've made my share of packages, either of internal software (the RPMs of common scripts and Nagios plugins that I put on all of the boxes) or of really new stuff that isn't available yet (Bacula in the CentOS repos is a full major version behind current).
I'm coming from an RPM based environment, so the terminology might not be the same, but the general idea should be...
I just keep a repository of every package I've ever built (in source form and as finished packages). As is required, I include dependency information in the RPM SPEC file, so it gets rolled into the RPM. When I want to know what the dependencies of a package I built were, I just "rpm -qpR foo.rpm", which lists the dependencies as reported by the RPM. If you want an exhaustive, recursive list you could just write a recursive script that uses that logic to check for dependencies of dependencies, etc.
If you're talking about lower-level, when I build packages I always keep the source under /buildroot, and for each package I generally keep two files: a screen log of the build process, and a "buildnotes" file. If there's any sort of weird dependency issues, I note it in buildnotes (which I generally roll into the package in /usr/share/doc/PACKAGENAME or some such location) - but for that stuff (human-readable dependencies, notes for packagers, etc - stuff more detailed than what the package format knows about dependencies) I haven't heard of any automated way of tracking it, save for a wiki or something in a makefile.