I've got Debian running on a Pentium 133, with 64 megs of memory. I also had it running on a Pentium 60 with 32 megs of memory (barely). I use the (faster) machine as a mail and proxy server. So yes, it can be done. I assume I could get the thing to run X-windows and stuff, but that's not needed for a server - I do remote administration using a SSH shell and/or Webmin.
One thing though - putting Linux on a laptop is not as easy as putting it on a regular PC. The reason is that laptops generally have rather exotic hardware. Check the specs before diving in, just to be sure it'll run. You could use Knoppix for that, IF the laptop has a cd-rom...
