In general, in x86-land, the Pentium M is the way to go -- as eee mentioned, it's much different from a P-IV, which results in it being significantly faster per MHz, and much stingier on power. (Even if you don't normally need a long battery life, it might come in handy sometimes, so it's not a bad thing to have a laptop with good battery life.) The 'Centrino' label only applies to machines with a Pentium M, a matching Intel chipset, and a matching Intel wireless card, as far as I know; a machine can have the same Pentium M and chipset, but if it doesn't have the wireless, it won't get the Centrino brand.
The big thing to check and double-check for any laptop is driver support in Linux. For example, the wireless card that's part of the Centrino-labelled units doesn't have a native Linux driver, and Intel, though suggesting there will be one someday, has been coy about when it will appear. Dell's 802.11g wireless cards ('truemobile', I think they're called) also don't have Linux drivers. On the other hand, there's the 'driverloader' thing from Linuxant, which is supposed to let you use the Windows driver in Linux; it apparently works well enough, at least with the Centrino wireless. In any case, the message here is to double-check hardware support before getting the thing, particularly wireless and video card support, typically the main sticking points for Linux on laptops.
If it were me looking today, I'd definitely give the greatest consideration to laptops from IBM and Apple, who, from what I've seen, consistently seem to put the most care and thoughtfulness into design and build quality. ThinkPads are remarkably solid machines, and people who have them tend to be satisfied with them (people particularly seem to love the keyboard quality). If money's no object, a T or X series model would be great, though the R seems nice enough, too, if you decide to save a few bucks. If it were me, I'd prefer an X series one, since portability (small, light) means most to me in a laptop. IBM also has a Cisco wireless card option on some configurations, which I think may have a proper Linux driver.
The iBook is definitely a terrific laptop -- when I was shopping about 6 months ago, that's what I chose (an 800 MHz iBook), and I've not been disappointed at all. Small and light (the 12" one, at least), great battery life, plenty fast (though a Pentium M would, I think, be faster than my G3), and very inexpensive given the quality of the thing. OS X is nice, but I use Gentoo on it all the time now, without a hitch. Since I got mine, Apple has bumped the iBook specs to include a G4, faster RAM, and a combo drive on all models, so it's an even better machine now. The only unfortunate change for us Linux users, however, is that the iBook now uses the 'Airport Extreme' card for wireless -- for which there's no Linux driver (Broadcom chipset), and there's no ppc equivalent of driverloader. There's no other card that fits in the Airport Extreme slot, and no PCMCIA on the iBook, either. So, to use wireless with Linux on a G4 iBook today, you'd need to use one of those little USB wireless thingys. For a bit more money, the PowerBooks are also sweet machines in every respect, though with the same wireless limitation in Linux; at least the 15" and 17" ones have PCMCIA, which increases the range of wireless alternatives. Oh, and before anyone shouts, "only one mouse button" -- remap the enter key (next to the space bar on an [i|Power]Book) to right-click, fn-enter to middle click (or, of course, your own preferred keys), and after a few minutes, you won't miss the extra buttons.
Otherwise, of recent laptops I've seen, Dells have been good, but not especially impressive (overall build quality and keyboard seemed a notch below IBM and Apple). Toshibas have not been impressive, though somone I know has one of the tiny, ultra-portable Portege ones running Red Hat, and loves it. Haven't seen any current models from other brands; I tend to see what friends have, and what the students and staff use at the uni where I work. I did see a nice-looking 'build-to-order' laptop in a computer shop recently; if you want to avoid an 'OS tax' embedded in the price, that might be worth checking. Unfortunately, as much fun as a person has shopping for these things, there's only so much time available...
