I guess a simple way of explaining it is that if there are any new header dependencies, one of the files that make already knows about must have been modified to add the #include statement, so make will correctly rebuild the .c file and generate the new .d file, even though it's working on outdated dependency information.

Though, I guess I wasn't quite correct either. See plorkyeran's sibling comment re: generated header files.