Pretty bad actually
AFAIK the current gen of Celerons and PIIIs actually come off the same production line - ie, they are the same chip. The difference is that the Celery has had half its onboard L2 cache disabled (exactly how this makes it cheaper is Intel's problem to figure out). For gamers, though, this is a big problem. Because of the high disparity between the internal speed of the CPU and the external speed of the system bus, modern systems depend on a fat cache to maintain high performance. In most business type environments the difference does not seem obvious (we use Celerons at work and they are fine) but UT really stresses your CPU, or rather, your system's ability to feed data to the CPU.
A well built system would probably play about 30% slower with a Celery rather than PIII under most circumstances. Celeron Front Side Bus is locked at 66 MHz too, BTW, compared to the 133 MHz Pentium III, I think. They overclock pretty well though, which helps.
If you need a good "budget" CPU, maybe consider the AMD Duron. It's better than a Celeron in price and performance, but motherboards are a bit scarce for them.