I recently bought a new laptop on eBay, an IBM Thinkpad (T41) (CNET review), and have installed Red Hat Fedora Core 5 on it. The partitioning of the hard drive was the main trick. I used the GNU Parted Live CD (linux.com review), and it worked quite well. You can download the ISO image and burn it to CD.

Some useful links:

1. Linux Thinkpad Wiki: Pre-Installation | Pre-Desktop Area | Wifi Set-up (Adapter Details | Madwifi Driver)
2. Installation Testimonials: FC1 on T41 | FC1 on T41P | FC 2 on T41 | FC3 on T41
3. Post-Installation How-To (lots of good advice about installing extra stuff)