I've found this question which is basically asking the same, but got no real answer.
Where is the make's config file / database file where it remembers the file timestamps, so it can tell what changed? I checked and there's no .make or similar in my project, nor in the home directory.
Or does it somehow store the information inside the files themselves, perhaps by modifying the timestamps? (That sounds fishy though)
There is no such "database". The program simply compare the filesystems modification and creation timestamps of source and target files.
Lets say you have the following rule:
some_target: some_source_1 some_source_2
Then if the modified timestamp of either some_source_1 or some_source_2 is later than the modification/creation time of some_target then the rule will activate and the target will be rebuilt.
Makefiles describe targets and dependencies. Make executes commands to create/recreate the target(s) if necessary.
If the target doesn't exist, then make will try to create it.
If the target does exist, make compares the modification times of the target and its dependencies. If any of the dependencies was modified after the target was modified, then make will execute the command(s) to regenerate the target.
For example, for C files the target is the corresponding .o file and the dependency is on the file containing the C source code (and possibly some include files). If the .c file is newer than the .o file, then make runs the C compiler. This will generate a .o file with a newer modification time than the .c file.