I'm not interested in the source code, I want to know how the C compiler (GCC) actually finds the functions. As in, when the preprocessor sees that I've included stdio.h, where does it look to find the files that define the function bodies?
Edit
I should probably also say I'm using Ubuntu 12.04, but if there's a general answer, that would work too.
gcc comes with (binary) object files (not C source files) which contain implementations of all the standard C functions. When you use gcc to link object files into an executable file, the linker automatically includes the object files which implement the standard library functions. According to this thread, that standard object file will probably be called libc.a or libc.so.
Say you include a call to printf in your program. When the linker tries to resolve where that call should go, it will find the definition of printf in libc.a, and make your function call point there.
Look at http://gcc.gnu.org/onlinedocs/gcc/Link-Options.html and note the -nostdlib and -nodefaultlibs options. You can use these options to tell gcc's linker not to include the standard library object files by default.