Как CMake понимает, что надо пересобрать main.cpp если поменялся включенный в него .h?

В этих .cpp есть специальные директивы «#include», вот их cmake ищет и складывает в кеш дату его модификации.

То, что нужно пересобрать, понимает не CMake, а make. Цель — исполняемый файл — протухает на фоне одной из своих зависимостей — заголовочного файла. Информация о зависимости скорее всего берется на основе анализа #include-ов (во времена pure Makefile-ов для этого юзали gcc -M).

во времена pure Makefile-ов для этого юзали gcc -M

https://cmake.org/Bug/print_bug_page.php?bug_id=11985

The Ninja generator uses gcc -M for gcc and a special tool for MSVC, and is therefore not affected by this bug. Other generators could be changed to behave like the Ninja generator.

Это ясно, но make не может сам придумать зависимости, может только исполнить записанные в Makefile. Если я напишу в Makefile, что a.out зависит от main.cpp, забыв указать что main.cpp завист от file.h, который в него включен, то make не имеет права сам вписать себе в Makefile зависимость main.cpp -> file.h, даже если она существует в природе реально.

Ну так мы ответили на твой вопрос? :)

то make не имеет права сам вписать себе в Makefile зависимость main.cpp -> file.h, даже если она существует в природе реально

С чего вы взяли? В классических Makefile была безусловная цель вызывающая gcc -M, которая генерировала .mk-инклуд с зависимостями. Не знаю уж как make это там переваривал - очевидно ему нужно было перечитать Makefile с инклудом после того как он появится. А CMake никто не мешает вызвать gcc -M самому и сразу сгенерить Makefile со всеми зависимостями. Хотя может у него и своя парсилка есть. Где - смотри в исходники.