You need to notify the recipients of changes being made.
Think of a person - like you - who discovers a new repository which solves some issue you have or which is a cool project. Where do you look what it does, what changed and who works on it? You usually go first to
- the readme file
- the changelog file
- the license file
- the copying file
Usually the whole repository is covered by one license - thus it also includes the instructions for the build system like Makefile
etc. If several licenses cover different files, the readme or license or copying file is also a good place to indicate that (additional to any header in the files themselves).
Further, it's good practise to summarize changes made in the readme or changelog file. That solves at the same time the issue that removed files cannot carry any changed headers due to their absence. Thus removal is easily indicated also like
Cleanup / Update: removed long out-dated port to OS/2 and updated build system for x86 to work with newer versions of gcc and clamp.
As to adding new files: Yes, it's good to add a header to them with project name, license indication and copyright statement - but it's not a requirement either. The important thing is, that recipients are clear under which license and under whose copyright a file falls. Thus I'd do both and also add it to the readme, changelog or copying file of the project indicating that you made changes (and roughly which).