1) It may not have a header file. But yes, in general, for large projects, you should have a header file if multiple translation units are going to use that function (don’t repeat yourself).
2) The linker searches through all the object files and libraries it was told about to find functions and other symbols.