Assuming Linux and glibc, you can either add /usr/local/lib to /etc/ld.so.conf (and run ldconfig) to add the directory to the usual runtime search path, or rebuild the library with -rpath=/usr/local/lib linker flag (if the linker is gcc itself, it should be -Wl,-rpath=/usr/local/lib instead).

Unfortunately, this stuff is much more platform dependent than Perl itself.