The Pentium M is mobile CPU in which I mean, its designed to use very little power. The celeron M is a diet version of the pentium M (like the regular celeron is to the p4). Stay away from it. Stick with the pentium M; it doesn't cost that much more, but the performence gain is noticiable.

A 1.6 ghz pentium M will not defeat a 2.6 p4 (we're talking stock speeds), though depending on the specific benchmark, the results are often very close. But also keep in mind, that the Pentium M will use far less power than a p4. Unless you need a powerful CPU in your latop for CPU intensive tasks (gaming is not one of them), stick with the pentium M. Its performence is enough, even for gaming. Its battery life is much longer, the laptop gets less hot and its lighter.

However, if you do video editing, or have scienctific applications running like mathematica, go for a latop with a desktop p4 CPU (yes, those laptops do exist, they're big heavy and are more transportable and than portable, battery life is shorter, much shorter than a pentium m). BTW, a pentium M CPU is more costly than a p4 CPU of equivalent performence.

If you really need mobile CPU power (like hollywood special effects teams), there are workstation latops Those things cost a fortune though (upwards of 10000, yes there are 4 zeros, not a typo).

BTW, above I mentioned at stock speeds, a pentium M overclocked can achieve some interesting results including the abilty to defeat some of the athlon64 FX CPU's in benchmarks. More info here:
http://www.tomshardware.com/cpu/20050525/index.html