The backing algorithms figure that out and include all the necessary patches, applying them in an order that works.

Without understanding the theory behind it, it sounds a lot like magic, but apparently it works.

That does sound like magic. If I made the following three commits in order, how would it figure out that the last commit depends on the first commit but not on the second one?

+ import foo

+ import bar

+ foo.hello()

That's not the sense of "depends on" that applies here. It's a textual relationship- in this case, I believe the last commit would depend on the second, which would depend on the first.

If you're familiar with CRDTs, they're closely related. Patches store enough information to commute, so a given state (e.g. a branch) can be described purely by a set of patches.