What are the complete rules for header file searching?

The exact behavior is implementation-defined (which means that it is supposed to be documented; Typically, headers named with <> syntax are searched for in one or more standard places. Header files named with "" syntax are first searched for in the ``current directory,'' then (if not found) in the same standard places. (This last rule, that "" files are additionally searched for as if they were <> files, is the only rule specified by the Standard.)
Another distinction is the definition of ``current directory'' for "" files. Traditionally (especially under Unix compilers), the current directory is taken to be the directory containing the file containing the #include directive. Under other compilers, however, the current directory is the directory in which the compiler was initially invoked. (Compilers running on systems without directories or without the notion of a current directory may of course use still different rules.)
It is also common for there to be a way (usually a command line option involving capital I, or maybe an environment variable) to add additional directories to the list of standard places to search. Check your compiler documentation.