Yeah, this is a little bit tricky (which is where a lot of devs use a tool to generate the makefile for them). You ideally need to work out the dependencies of each cpp to work out which header they rely on. GCC does support this with the use of .d files. I have never really looked into this.
but I can't understand how that would handle recompilation in the case a header file included by the source is modified
Personally... when working with a smallish project I just get a list of all my .h files and add them as a rule dependency. I.e if any header in the project changes, the whole thing gets re-compiled.
When I work on a large project... I break the project up into seperate modules (each with their own Makefile) and am back to working with a smallish project ;D