Dynamic executables have a symbol table used by the linker to resolve links that need to be connected to library functions. (You can verify this by running objdump -T /path/to/binary ).
This symbol table is available for other tools - for example, ltrace - so it is trivial to determine which functions need to be hooked and go through this list individually.
See the talk on internal ltrace data presented at the Ottowa Linux Symposium, which contains a detailed breakdown of functions; Follow the source, see the official repository or third-party github mirror .
Some newer versions (later than these conversations) also include the dlopen() call to track calls to dynamically loaded libraries. The mechanism there should be fairly obvious at one point: if you replace dlopen() with a pad (when dlopen() itself is dynamically connected, as described above), then you can set a breakpoint on any function pointer returned.