When ld-linux resolves a symbol it searches through the shared libraries in a particular order and stops when it finds a shared library with a matching symbol.
What determines the order it searches through the libraries? Does it make a difference if the unresolved symbol is in the main program or in another shared library?
How could I determine the search order programatically without calling external programs like ldd?
This book http://www.network-theory.co.uk/docs/gccintro/gccintro_18.html suggests left-to-right order as given on the gcc command line. (I learned long ago to always place -lm as the very last library in a list of libraries to link with, but I've also long since forgotten the cargo-cult reason for that.)
EDIT
Aha, thanks for the update. You're going to need to parse the ELF yourself; look for "Shared Object Dependencies" and "DT_RPATH" in http://www.muppetlabs.com/~breadbox/software/ELF.txt. (I also recommend http://www.muppetlabs.com/~breadbox/software/tiny/teensy.html, but it's less applicable to your problem -- just fun reading.)
/usr/include/linux/elf.h has all the typedefs.
From http://www.muppetlabs.com/~breadbox/software/ELF.txt (as mentioned by sarnold):
When resolving symbolic references, the dynamic linker examines the symbol tables with a breadth-first search. That is, it first looks at the symbol table of the executable program itself, then at the symbol tables of the DT_NEEDED entries (in order), then at the second level DT_NEEDED entries, and so on.