LD_LIBRARY_PATH vs LIBRARY_PATH

LIBRARY_PATH is used by gcc before compilation to search directories containing static and shared libraries that need to be linked to your program.

LD_LIBRARY_PATH is used by your program to search directories containing shared libraries after it has been successfully compiled and linked.

EDIT: As pointed below, your libraries can be static or shared. If it is static then the code is copied over into your program and you don't need to search for the library after your program is compiled and linked. If your library is shared then it needs to be dynamically linked to your program and that's when LD_LIBRARY_PATH comes into play.

Since I link with gcc why ld is being called, as the error message suggests?

gcc calls ld internally when it is in linking mode.

LD_LIBRARY_PATH is searched when the program starts, LIBRARY_PATH is searched at link time.

caveat from comments:

• When linking libraries with ld (instead of gcc or g++), the LIBRARY_PATH or LD_LIBRARY_PATH environment variables are not read.
• When linking libraries with gcc or g++, the LIBRARY_PATH environment variable is read (see documentation "gcc uses these directories when searching for ordinary libraries").