The Centrino brand denotes a chipset, not a processor. All Centrino laptops use Pentium M processors, but the reverse is not true; usually non-Centrino laptops are very similar, but just use dedicated Wi-fi instead of the built-in Centrino chip (and the dedicated chip is most often better, so don't just go shopping with Centrino in mind).
The Sempron is a value-minded AMD processor. The Celeron is a value-minded version of the Pentium 4. The Celeron-M is a value-minded version of the Pentium M. I would avoid all of these processors, unless you specifically don't want your machine to last for a while and have to save money at all costs. I've played with the Celeron and Celeron M, and was not impressed.
I would actually only consider buying a Pentium M for a notebook, because it gives by far the best all-around value when you consider performance and battery life. If battery life is not a consideration at all, the A64 is currently the best choice; it's fast and pretty cheap to boot.
Pentium M laptops tend to be thinner and lighter than the competition, have excellent performance, and have great battery life. You also don't have to break the bank to get a great chip. The fastest Pentium M out so far runs at 2.1Ghz, and will cost a pretty penny. However, a 1.5 or 1.6Ghz will be screaming-fast by most people's standards, believe me.
If you buy a Pentium M, make sure to find out the cache size. Pentium Ms are still sold in two versions, named "Banias" (older) and "Dothan" (newer). Even if it costs slightly more for a similarly-clocked chip, try to get a Dothan. It offers even lower power consumption than that of the (still excellent) Banias, and it also has 2MB of level 2 cache, whereas Banias has 1MB. This allows a Dothan to outperform a similarly-clocked Banias by a margin of around ten percent for most tasks.