As Ignacio says, .a files are static libraries. The "a" stands for "archive" and .a files are built by a program named "ar".
Each .a file contains one or more .o files and an index of names. During the link process only the .o files that contain used names are included into the final program. This is so that instead of including the entire C library, only used functions like "printf" are copied.
How does the compiler find the libraries? It has a built-in collection of library paths that are searched. As an example, GCC will tell you its search paths if asked:
# gcc -print-search-dirs
install: /usr/lib/gcc/i686-redhat-linux/4.4.4/
programs: =/usr/libexec/gcc/i686-redhat-linux/4.4.4/:/usr/libexec/gcc/i686-redhat-linux/4.4.4/:/usr/libexec/gcc/i686-redhat-linux/:/usr/lib/gcc/i686-redhat-linux/4.4.4/:/usr/lib/gcc/i686-redhat-linux/:/usr/libexec/gcc/i686-redhat-linux/4.4.4/:/usr/libexec/gcc/i686-redhat-linux/:/usr/lib/gcc/i686-redhat-linux/4.4.4/:/usr/lib/gcc/i686-redhat-linux/:/usr/lib/gcc/i686-redhat-linux/4.4.4/../../../../i686-redhat-linux/bin/i686-redhat-linux/4.4.4/:/usr/lib/gcc/i686-redhat-linux/4.4.4/../../../../i686-redhat-linux/bin/
libraries: =/usr/lib/gcc/i686-redhat-linux/4.4.4/:/usr/lib/gcc/i686-redhat-linux/4.4.4/:/usr/lib/gcc/i686-redhat-linux/4.4.4/../../../../i686-redhat-linux/lib/i686-redhat-linux/4.4.4/:/usr/lib/gcc/i686-redhat-linux/4.4.4/../../../../i686-redhat-linux/lib/:/usr/lib/gcc/i686-redhat-linux/4.4.4/../../../i686-redhat-linux/4.4.4/:/usr/lib/gcc/i686-redhat-linux/4.4.4/../../../:/lib/i686-redhat-linux/4.4.4/:/lib/:/usr/lib/i686-redhat-linux/4.4.4/:/usr/lib/
You can add more library search paths by using the "-L /path" option.
In those paths, it first searches for "dynamic libraries" which are named with a ".so" extension. It then searches for static libraries with a ".a" extension. It always adds "lib" to the front of the name.