Depende de onde o arquivo está, no meu caso funciona assim:
:~$ locate gcc_s
/lib/x86_64-linux-gnu/libgcc_s.so.1
/usr/lib/gcc/x86_64-linux-gnu/4.6/libgcc_s.so
/usr/lib/gcc/x86_64-linux-gnu/4.7/libgcc_s.so
E você precisa ter certeza de que o caminho está presente em um dos arquivos ld.so.conf como:
:~$ cat /etc/ld.so.conf.d/x86_64-linux-gnu.conf
# Multiarch support
/lib/x86_64-linux-gnu
/usr/lib/x86_64-linux-gnu
Mas este é o Debian x86_64
:~$ gcc -lgcc_s sample.c -o sample
:~$ ldd sample
linux-vdso.so.1 => (0x00007fff6a9ff000)
libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 (0x00007f8e95a29000)
libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f8e9569f000)
/lib64/ld-linux-x86-64.so.2 (0x00007f8e95c4a000)