The .dynamic section of an ELF file (.so libraries on Linux use ELF format) contains information to help the library find its dependencies. .dynamic entries with type DT_NEEDED contain the names of other .so files for the dynamic linker to find, but they do not contain any information on where to find those files. For that, as you mentioned, you can use LD_LIBRARY_PATH, but the ELF format also provides a way to specify it in the file itself.
A .dynamic entry with type DT_RUNPATH gives the dynamic linker a path to a directory where the dynamic linker should look for DT_NEEDED files. DT_RUNPATH allows a special variable, $ORIGIN, which refers to the file's current directory. This allows you to use relative paths, without requiring the user to invoke an executable from a specific working directory.
You use the -rpath linker flag to specify a DT_RUNPATH entry. In order to pass the literal string $ORIGIN, however, you must wrap it in single quotes to prevent your shell from interpreting it as an environment variable.
Assuming you are using gcc, you should use add this argument to the link step:
-Wl,-rpath,'$ORIGIN'