If your program is a normal ELF executable, then you can (apparantly) set the DT_RUNPATH tag to a list of directories to search for the library. How you do this I do not know.
Personally, I would suggest that you use setenv() to append the additional directories to the LD_LIBRARY_PATH variable, like this:
Code:
char * path = getenv("LD_LIBRARY_PATH");
char buffer[strlen(path)+100];
sprintf(buffer,"%s:%s",path,"/other/path/here");
setenv("LD_LIBRARY_PATH",buffer,1);
Note that you should also test if path is NULL before calling strlen (to avoid a segmentation fault if LD_LIBRARY_PATH is not defined).
Edit: This will only affect your app (and any child processes your app spawns); you should do this before calling dlopen().