Where do executables look for shared objects at runtime?

The shared library HOWTO explains most of the mechanisms involved, and the dynamic loader manual goes into more detail. Each unix variant has its own way, but most use the same executable format (ELF) and have similar dynamic linkers¹ (derived from Solaris). Below I'll summarize the common behavior with a focus on Linux; check your system's manuals for the complete story.

(Terminology note: the part of the system that loads shared libraries is often called “dynamic linker”, but sometimes “dynamic loader” to be more precise. “Dynamic linker” can also mean the tool that generates instructions for the dynamic loader when compiling a program, or the combination of the compile-time tool and the run-time loader. In this answer, “linker” refers to the run-time part.)

In a nutshell, when it's looking for a dynamic library (.so file) the linker tries:

• directories listed in the LD_LIBRARY_PATH environment variable (DYLD_LIBRARY_PATH on OSX);
• directories listed in the executable's rpath;
• directories on the system search path, which (on Linux at least) consists of the entries in /etc/ld.so.conf plus /lib and /usr/lib.

The rpath is stored in the executable (it's the DT_RPATH or DT_RUNPATH dynamic attribute). It can contain absolute paths or paths starting with $ORIGIN to indicate a path relative to the location of the executable (e.g. if the executable is in /opt/myapp/bin and its rpath is $ORIGIN/../lib:$ORIGIN/../plugins then the dynamic linker will look in /opt/myapp/lib and /opt/myapp/plugins). The rpath is normally determined when the executable is compiled, with the -rpath option to ld, but you can change it afterwards with chrpath.

In the scenario you describe, if you're the developer or packager of the application and intend for it to be installed in a …/bin, …/lib structure, then link with -rpath='$ORIGIN/../lib'. If you're installing a pre-built binary on your system, either put the library in a directory on the search path (/usr/local/lib if you're the system administrator, otherwise a directory that you add to $LD_LIBRARY_PATH), or try chrpath.

In Linux the behavior is explicited in the ld(1) man page

       The linker uses the following search paths to locate required
       shared libraries:

       1.  Any directories specified by -rpath-link options.

       2.  Any directories specified by -rpath options.  The difference
           between -rpath and -rpath-link is that directories specified by
           -rpath options are included in the executable and used at
           runtime, whereas the -rpath-link option is only effective at
           link time. Searching -rpath in this way is only supported by
           native linkers and cross linkers which have been configured
           with the --with-sysroot option.

       3.  On an ELF system, for native linkers, if the -rpath and
           -rpath-link options were not used, search the contents of the
           environment variable "LD_RUN_PATH".

       4.  On SunOS, if the -rpath option was not used, search any
           directories specified using -L options.

       5.  For a native linker, the search the contents of the environment
           variable "LD_LIBRARY_PATH".

       6.  For a native ELF linker, the directories in "DT_RUNPATH" or
           "DT_RPATH" of a shared library are searched for shared
           libraries needed by it. The "DT_RPATH" entries are ignored if
           "DT_RUNPATH" entries exist.

       7.  The default directories, normally /lib and /usr/lib.

       8.  For a native linker on an ELF system, if the file
           /etc/ld.so.conf exists, the list of directories found in that
           file.

       If the required shared library is not found, the linker will issue
       a warning and continue with the link.

I'm pretty sure the answer here is ldconfig.

ldconfig creates the necessary links and cache to the most recent shared libraries found in the directories specified on the command line, in the file /etc/ld.so.conf, and in the trusted directories (/lib and /usr/lib). The cache is used by the run-time linker, ld.so or ld-linux.so. ldconfig checks the header and filenames of the libraries it encounters when determining which versions should have their links updated.

http://linux.die.net/man/8/ldconfig