Use apt-file search [filename]
para determinar o pacote que fornece esses arquivos, bem como sua localização.
libX11.a:
libx11-dev: /usr/lib/x86_64-linux-gnu/libX11.a
libX11.so:
libx11-dev: /usr/lib/x86_64-linux-gnu/libX11.so
Xlib.h:
libx11-dev: /usr/include/X11/Xlib.h
Então, sim, você já deve tê-los.