I recently had to build LWJGL on linux (more specifically, Ubuntu dapper), and this is what i basically had to do (with a little help from Mojomonkey):
install java through synaptic
set env. variable JAVA_HOME to point to /usr/lib/jvm/java-*
download FMOD and set env. variable FMOD to point to to the directory
sudo apt-get install build-essentials
sudo apt-get install libxt-dev
sudo apt-get install libxcursor-dev
sudo apt-get intstall libxrandr-dev
sudo apt-get install x11proto-xf86vidmode-dev
sudo apt-get install libxxf86vm-dev
Thats pretty pretty much all you need, then simply run -compile_linux as the ant target of the LWJGL makefile.
PS, the * points to the java version, as of this writing, its java-1.5.0-sun
Enjoy,
DP :)