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

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 uses the above mentioned Intel TBB library.

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.