The Celeron's roots
Intel's original plan for the Celeron processor was to take AMD head-on in the lower margin, "budget-performance" market. To target this ever-increasing niche, Intel simply needed CPUs which they could sell at a highly discounted price. In order to realize the cost reductions, Intel removed the L2 cache from the Celeron entirely, and then removed the plastic SEPP cartridge that housed the circuit board (PCB).
To further emphasize the performance difference between the Celeron and PII lines, Intel put the Celeron on a 66 MHz bus, and paired the Celeron up with the LX chipset, which is less robust than the BX chipset. Coupled with its already-missing L2 cache, the performance difference between the two lines was clearly delineated. Two versions of this first-generation Celeron were released, running at 266 MHz and 300 MHz. The end result was a naked and stripped down Celeron which, largely due to its lack of L2 cache, left a bad taste in consumers' mouths.
The next generation
After a brief fiasco, Intel spun around 180 degrees and put L2 cache back into the Celeron. Still intended as the budget CPU, the Celeron was given 128K of L2, which is ¼ the size of the L2 cache found on its "big brother" Pentium II, which has 512K. The surprising development, though, was that the L2 cache found on the Celeron was clocked at full CPU clock speed, meaning that a 300 MHz Celeron CPU would have its L2 cache also running at 300 MHz. In the Pentium II line, the L2 cache runs at ½ of the processor's clock speed. The first of the new Celerons was clocked at 300 MHz, and began ramping up in speed from there.
However, with the negative association the public had with the Celeron name, early sales were not great. It was not until benchmarks began to show that Celerons, with 128K L2 cache running at full CPU speed, were holding their own against their PII counterparts at the same clock speeds, but for a fraction (typically 1/3 to 1/2) of the price. Then, CPU tweakers discovered how friendly the Celeron line was to overclocking. As a result, nowadays Celerons are commonplace among gamers and home users alike.