Где в linux искать библиотеки для GCC?

Библиотеки обычно устанавливают в /usr/lib/, /usr/local/lib и их подпапки. Обычно эти пути и так находятся в LD_PATH, так что достаточно указать -l<libname>.

Так же библиотеки часто устанавливаются вместе с pkg-config конфигурацией, так что можно использовать его так:

gcc -c file.c `pkg-config --cflags <libname>`
gcc file.o -o file `pkg-config --libs <libname>`

Можно установить утилиту locate, и искать всё что вашей душе угодно. Можно посмотреть в пакетном менеджере куда и что устанавливается. Но обычно, компилятор видит библиотеки, установленные по дефолту (в места по-умолчанию), вам надо только -l и имя библиотеки добавить во флаги линкера.