Dependency tracking is performed as a side-effect of compilation. Each time the build system compiles a source file, it computes its list of dependencies (in C these are the header files included by the source being compiled). Later, any time make is run and a dependency appears to have changed, the dependent files will be rebuilt.
Automake generates code for automatic dependency tracking by default, unless the developer chooses to override it; for more information, see Dependencies.
When configure is executed, you can see it probing each compiler for the dependency mechanism it supports (several mechanisms can be used):
~/amhello-1.0 % ./configure --prefix /usr
...
checking dependency style of gcc... gcc3
...
Because dependencies are only computed as a side-effect of the
compilation, no dependency information exists the first time a package
is built. This is OK because all the files need to be built anyway:
make does not have to decide which files need to be rebuilt.
In fact, dependency tracking is completely useless for one-time builds
and there is a configure option to disable this:
Some compilers do not offer any practical way to derive the list of dependencies as a side-effect of the compilation, requiring a separate run (maybe of another tool) to compute these dependencies. The performance penalty implied by these methods is important enough to disable them by default. The option --enable-dependency-tracking must be passed to configure to activate them.
See Dependency Tracking Evolution, for some discussion about the different dependency tracking schemes used by Automake over the years.