Let me describe a way which works through all systems and simplifies the distribution of library code within a package a lot.

First I want to point out that there are two major scenarios here:

1. You are currently developing a package containing `LibraryLink` functions.
When you are actively working on such a package, it is most likely not installed in your `$UserAddOnsDirectory` but instead in your development path.
Nevertheless, you want to test, debug or run your library functions within *Mathematica*. On those development machines I find it quite convenient to either set the *Mathematica* `$LibraryPath` variable or provide the appropriate environment variables to *Mathematica*. The latter can be annoying sometimes, especially on OSX because they change the way of sending env-variables to applications every five minutes.

2. The second scenario is when you have finished your package development and it is ready to be installed (or distributed to other machines). Here, there is a much easier way to solve the dependency problem which I will describe in the following

###Set up your package structure correctly

Your package should have the library functions and dependency libraries in the appropriate folder under `Package/LibraryResources/$SystemID`. As example, here the directory structure of one of my projects

<!-- language: lang-none -->

    IPCU
    ├── Documentation
    │   └── English
    │       └── ReferencePages
    │           └── Symbols
    ├── Java
    ├── Kernel
    └── LibraryResources
        ├── Linux-x86-64
        ├── MacOSX-x86-64
        ├── Windows
        └── Windows-x86-64

The overall advantage of putting a package structured like above into a place where *Mathematica* can find it is that it will automatically add the correct library path to its `$LibraryPath` variable and all `.so|.dylib|.dll` will be found.

### Loading the dependencies *before* your `LibraryFunction`

Now you can first check that all your libraries can be found even if you haven't set any environment variable explicitly or hard-coded the library position like in Szabolcs answer. To give an example for my package:

    (* on Linux *)
    FindLibrary["libtbb"]
    (* /home/patrick/.Mathematica/Applications/IPCU/LibraryResources/Linux-x86-64/libtbb.so *)
    
    (* on OSX *)
    FindLibrary["libtbb"]
    (* /Users/patrick/Library/Mathematica/Applications/\
      IPCU/LibraryResources/MacOSX-x86-64/libtbb.dylib *)

Now, what you have to do is to load all dependency libraries before you load you actual `LibraryLink` functions. Please be careful, because order might be important. If you get an error, please check the content of ``LibraryLink`$LibraryError``, which gives a more detailed reason for failure.

To grab an example, the underlying parallel *LibraryLink* function from [my answer here](https://mathematica.stackexchange.com/a/26750/187) uses the above mentioned [Intel TBB library](http://en.wikipedia.org/wiki/Threading_Building_Blocks). 

If I just try to load the `calculateNewtonFractal` *LibraryLink* function, I get the following error 

> LibraryFunction::libload: The function calculateNewtonFractal was not loaded from the file /home/patrick/.Mathematica/Applications/IPCU/LibraryResources/Linux-x86-64/ipcu_library.so.

and the content of ``LibraryLink`$LibraryError`` is 

> "libtbb.so.2: cannot open shared object file: No such file or directory"

If I instead preload the tbb, it works excellent:

    LibraryLoad["libtbb"];
    cNewtonFractalShared=LibraryFunctionLoad[
      "ipcu_library","calculateNewtonFractal",
      {{_Complex,1,"Constant"},{_Real,1,"Constant"},{_Real,1,"Constant"}, 
       {_Real,0,"Constant"},{_Integer,3,"Shared"}},"Void"]
    
    (* LibraryFunction[<>,calculateNewtonFractal,{{Complex,1,Constant},
    {Real,1,Constant},{Real,1,Constant},{Real,0,Constant},{Integer,3,Shared}},{}] *)

###Conclusion

Therefore, the condensed required steps are:

1. Make sure your dependency libraries can be found with `FindLibrary` by (i) using above package structure, (ii) setting `$LibraryPath` manually or (iii) setting system environment variables and providing them to *Mathematica*.
2. Load the dependency libraries in the correct order (they might depend on each other) using `LibraryLoad`. Check ``LibraryLink`$LibraryError`` if you get errors.
3. Load your *LibraryLink* function using `LibraryFunctionLoad`.