25
$ locate libX11
/Developer/SDKs/MacOSX10.4u.sdk/usr/X11R6/lib/libX11.6.2.dylib
/Developer/SDKs/MacOSX10.4u.sdk/usr/X11R6/lib/libX11.6.dylib
/Developer/SDKs/MacOSX10.4u.sdk/usr/X11R6/lib/libX11.a
/Developer/SDKs/MacOSX10.4u.sdk/usr/X11R6/lib/libX11.dylib
/Developer/SDKs/MacOSX10.5.sdk/usr/X11/lib/libX11.6.2.0.dylib
/Developer/SDKs/MacOSX10.5.sdk/usr/X11/lib/libX11.6.dylib
/Developer/SDKs/MacOSX10.5.sdk/usr/X11/lib/libX11.dylib
/usr/X11/lib/libX11.6.2.0.dylib
/usr/X11/lib/libX11.6.dylib
/usr/X11/lib/libX11.dylib
/usr/X11/lib/libX11.la
I'd try
gcc [...] -L/usr/X11/lib -lX11 [...]
to set the search path for libraries.
Ubuntu 12.10 (And probably others) require sudo apt-get install libx11-dev.