I'm sure someone will correct me on this but the "M" stands for, well, duh....MOBILE. Ther pentium M chips are also referred to as Centrinos also, basically they are cpus which are desinged for portables, which means they are designed to run at lower voltages than their desktop counterparts which means you'll have a longer battery life with that class of processor. Celerons are just budget versions of pentiums. As far as things like L2 cache are concerned, more generally means faster, but for the average user who isn't gaming or video editing or sound editing L2 means basically very little. So your average user who is going to surf the web, use an office app or listen to music there probably not going to notice any difference between a Cely and a Pentium.
What will make a difference especially with laptops and especially with the brands listed is more memory. So consider a less powerful processor to afford more memory, most come with 256MB these days but double that and the thing will feel faster.
I'm with Bonk, find the cheapest laptop with an "M" class processor, double the memory, get rid of "the bloat" and you'll bet set. I reference "the bloat" because most prebuilts from the large manufacturers come loaded with software, software that a lot of us don't need which loads at start up and slows the computer down. Me persoanlly I would buy from a shop like PC Club, where the software install would be at a minimum, and I would get an actual copy of Windows Xp and not just a "restore' disk. But the best deals are going to be found at the large retailers.