How much faster? I'd say ~2 times (in terms of number crunching). You're going from a 66FSB to a 100FSB, but also from a 512k L2 cache down to 128k.
It all depends what you want to do.
I put a celeron-500 in my ~new laptop (because of the ultra low power consumption) and it works fine for all my office apps and light gaming (Diablo II, Age of Empires II,...) needs. Just make sure you have enough memory (256mb). The Celeron-800 is only ~US$50.
If you want to play the latest 3D games, I wouldn't bother.
With more information on your current system and what you want to do with it we might be able to provide a better opinion.
It would be better for things like word processing and your everyday internet surfing. However if you plan on doing any gaming besides solitaire, I would stick with the Pentium line of processors. Chances are, with a BIOS upgrade your board will support up to a 1.0GHz Pentium III and lower. Let us know what motherboard you have along with some other system specs and we can give you more precise and educated answers.
<font color=red>"I'm not gonna launch a $2 million missile at a $10 tent and hit a camel's butt." -Bush</font color=red>
I'm fairly certain your motherboard has a 133MHz FSB setting. That leaves you wide open for the PIII -EB series. If not, the -E series are still considerably better performing than the Celeron. Based on my testing I estimate the PIII 850 will outperform a Celeron 1.1GHz slightly, but a PIII 800EB (that's the 133MHz FSB version) will do about the same. So if your able to get the 133MHz FSB, the 800EB, 866, 933, and 1000EB are your best choices.