Intel calls their budget CPUs Celerons. There are three* different current CPUs that Intel calls Celerons these days.
By far the most common of these is 'Northwood'-based Celeron. It's basically a Pentium 4 with 128K of level-2 cache (really fast memory that's used instead of your system RAM whenever possible) instead of the 512K that 'Northwood'-based Pentium 4s have, and a 400MHz 'front side bus', rather than the 533MHz or 800 MHz of a Pentium 4 (so the CPU communicates with the rest of the system at a lower speed). The problem with this is that the Pentium 4 architecture is really dependent on memory bandwidth, so small amounts of cache and slow bus speeds are really bad. Even the fastest Northwood-based Celerons (2.8 GHz) aren't as fast as the slowest Northwood-based Pentium 4s. This Celeron is one that you should never buy, unless it's in a very cheap system that will never be used for gaming or any other demanding applications.
Intel has just released a new Celeron, called the Celeron D, which is based on the 'Prescott' core. It's nowhere near as crippled as the 'Northwood' Celeron, as it's got 256K of level 2 cache and 533 MHz front side bus; the Prescott-based Pentium 4 'E' has 1MB of level 2 cache and an 800 MHz front side bus. This chip actually is a decent low-end CPU (a Pentium 4 E clocked at the same speed as a Celeron D is significantly faster, but nowhere near to the same degree), but it's really new. You still don't want to use it in a high-end gaming box, though.
And in some notebooks, you'll see Intel's Celeron M CPU. This one is based on the Pentium M (the CPU in any notebook with a Centrino label). Since the Pentium M is an excellent notebook CPU, Celeron M based notebooks aren't half bad either. Like all Celerons, the Celeron M has less level 2 cache than its 'big brother', but in the case of the Celeron M, it's got half the cache of the Pentium M, rather than one quarter, runs at the same front side bus speed, and the Pentium M design is nowhere near as dependendent on memory bandwidth as the Pentium 4 design (so the difference in cache matters far less). The main problem with these is that they tend to be clocked somewhat slower than their Pentium M based cousins.
* Technically, there are four. The Xbox CPU is an older, Pentium III-based Celeron. But I think that's the only way you can easily get that version of the Celeron anymore.