The reason this is tractable is that Nix packages are written in an expressive language. Most package definitions are actually functions, which accept their dependencies as arguments. Such functions provide flexibility, making it easy to switch out dependencies or perform other changes, and are often passed around using higher-order functions. The closest thing to dependency resolution is to take the fixed-point of a function, which is used to populate each package's dependency arguments using the other packages (which we're also populating the arguments of; this relies on Nix being lazy!).
For example, the `cabal2nix` tool can read a Haskell '.cabal' file and create a Nix function, which accepts dependencies and returns a package. We can turn this into a concrete package by specifying a version of Haskell to use (e.g. `haskell.ghc7103` for GHC 7.10.3, `haskell.ghc801` for GHC 8.0.1, `haskell.ghcjs` for GHCJS, etc.); each contains a higher-order function `callPackage`, which we pass our generated function to, along with any non-default overrides.
For example, we can run the command:
nix-shell -p "(haskell.ghc7103.callPackage ($(cabal2nix /path/to/project.cabal)) { some-dep = my-version-of-some-dep; })"
This will drop us into a bash shell where the Haskell project at /path/to/project.cabal has been built using GHC 7.10.3, with default versions of all dependencies except for "some-dep" which we override to be some other package. If, for example, our Haskell package defines a bunch of executables, they'll be available in this shell's $PATH.There are also higher-order functions like `ghcWithPackages` for defining Haskell environments with pre-populated package databases, `override` which takes the fixed-point of a set of packages (so overriding "foo" ensures that all packages depending on "foo" get our version, transitively), etc.
On the other hand, if A and B provide (some sort of) libraries which C imports, then their dependencies may be exposed by appearing in the pool of libraries available to C. This is certainly the case for Haskell, where all of a library's dependencies accumulate in the ghc-pkg database and multiple versions of a library aren't allowed in the same program. As you say, such things are existing problems in external, language-specific tools, and aren't caused by Nix; although Nix may provide a useful abstraction to better manage such problems.
* There may be application-specific problems at runtime, e.g. if A and B try to de/serialise each other's data, but I'd count that as a bug: if A and B are meant to be standalone then they're buggy, as their I/O formats should be more robust; on the other hand, if A and B are meant to be used together then the packaging is buggy: A and B should expose their shared dependency as a parameter, and C should pass in the same version to both.