For me there a several factors that would affect that decision....
First portability/size >>> The PIIIm acrcitecture is available in many ultra portables such as the IBM x21 and Dell Latitudes. The Current P4 Celeron offerings, really have no great portability options. they are targeted at budget users, who think and laptop is a laoptop, and as such will be getting a slower bulky unit.
Second, speed/performance. >>> The PIIIm is pretty similar to the Pentium M. The P-M basically is a souped up PIII. If portability was not a factor I would go with a higher end PIIIm chip (1-1.2 GHz). I would only go with a P4 celeron chip at 2.53 gHz or higher... To me this is the cut of where you would get better across teh board performance out of the celeron compared to the PIII.
Overall I feel that the PIIIm platform is better made and more reliable. Granted it is using older supporting hardware, so it may be hard to find units with built-in Wi-Fi/Bluetooth, and DDR RAM is out of the question. Bottom line, I wouldn't touch a celeron laptop from a performance standpoint under 2.53 GHz. The crazy part about that is that once you get up in those high numbers it will start producing more and more heat, and using more juice.... So its really a sort of Catch 22.
The celeron-M (Penium-m derivative) is a decent performer, and I would highly suggest looking into that chip as a budget laptop solution as opposed to the P4-Celeron.