That means you don't have the libsdl-dev package installed.
Here (Ubuntu 7.10) the package it's called "libsdl1.2-dev"
You'll also need the -dev versions of libsdl-ttf, libsdl-net and libsdl-image.
This is mentioned in the homepage, but it should also be in the
README, I'll fix it.
Regards,
bart9h