Companies like PowerLogix, NewerTech, Sonnet, and Daystar all produced 3rd party CPU upgrades for all kinds of Macs (Search on those names).

For example; a Sonnet G4 upgrade card for AGP Macs & others (via Wayback Machine).

Its likely the above companies no longer produce these products, which will mean finding one 2nd hand. - They'd be expensive if new anyway.

It might be easier and cheaper to purchase a 2nd hand Mac G4 tower with the specs you need already built-in (e.g; QuickSilver 2002 or MDD)

I think you can find a G4 733 or 867 Quicksilver for $75 in most places.
I have a friend who has about 20 of them used in his shop (in RI). Check you local Craigslist.
A used Sonnet upgrade card is going to run you $30-40 used on ebay.
And there's no guarantee that it won't be subject to thermal runaway at this point in time.
An Apple 867 CPU chip is going to be easier to find and cheaper to replace.

Don't forget you are limited to drives of 128GB or less by the built in ATA specs of the early G4 lines (pre MDD). You can get around that with either a Sonnet PCI SATA card or a Sonnet PCI ATA100 or ATA133 card. This is a hard limit of ATA33/66 and has nothing to do with the OS used.

I have always found the Quicksilvers to be the most dependable. Especially if you plan on running OS 9 as your base OS. The MDDs ran too hot IMHO and installing OS 9.2.2 on them can be a pain.

Hardcore Mac has some CPU upgrades for various old Macs listed. I have never bought anything from there (because the prices tend to be over-bloated), so I cannot vouch for the quality of their service.

As others have said, you can probably find a newer Mac model cheaper than buying that one and upgrading it ... BUT that one is in a local store, so can be picked up, rather than paying an extra large price to have the big, heavy computer delivered.

How much you can upgrade it depends on which model-exactly-it is.

The "Graphite" case models actually came in four variants-the Yikes!(PCI graphic), Sawtooth(AGP graphics), Gigabit Ethernet, and Digital Audio. Aside from the obvious differences as implied by the names, the Gigabit Ethernet added the ability to ADC displays, and the Digital Audio is really more like a Quicksilver inside than the earlier models(it has 3 RAM slots, 4 PCI slots, and a 4x AGP socket).

The PCI graphics model is really something of a dead end as far as upgrades. It uses a ZIF socketed processor and is really very similar internally to the B&W G3. Some companies made aftermarket processors, but I don't think these got overly fast. You can also use the jumpers on the board to overclock it, although you can potentially be playing with fire by doing this(at a minimum you will want to add a CPU fan, and can probably not stably get more than an extra 50-100mhz).

Any of the other three models have a lot more options as far as processor upgrade. Any factory processor can be freely interchanged between any AGP socketed, graphite cased G4. Probably best-depending on your use-is either the 733mhz or the dual 533mhz out of the Digital Audio(some OS 9 apps benefit from dual processors, but most don't). Any "Quicksilver" processor will also work, although you need to provide an additional +12V to one of the screw holes on the processor card. The best of the bunch is the dual 1ghz processor, although these are tough to find. In general, you should try to buy the processor and heatsink as a pair, and transplant both. This is essential if you are upgrading from a single to a dual processor.

Quicksilvers have better processor options to start with, and all Quicksilver processors are freely interchangeable. The caveat is that if you transplant a processor with L3 cache into a computer that was not built with it(namely the low-end 733mhz model and low-end 800mhz QS2002), you will not be able to access the L3 cache. In real world use, this probably makes a bigger difference than a faster clock speed.

MDD models came in two bus speeds-133mhz and 167mhz. The low end, dual 867 mhz MDD and MDD2003 models had a 133mhz bus, as did the dual 1ghz FW800 model. Aside from bus speed differences, the processors can be freely interchanged(again, keep the heatsinks with the processors). Bear in mind that the FW800 models can not natively boot into OS9. Also, if you are getting an MDD or MDD2003(both of which can natively boot into OS 9) be sure you get the restore disks-they are next to impossible to locate on their own, and necessary to install OS 9 on these computers. Many folks consider the MDD2003 single 1.25ghz the "king" of OS 9 machines.

Of the later (OS 9 native capable) Mac towers, the Digital Audio and Quicksilver models were my favorites - but not so with the dual CPU models which I had PSU failures with. The single CPU range seemed more reliable to me. The MDD I never went for - didn't like the case design and the reports of "wind tunnel" syndrome put me off. Apple offered fan & psu swaps not long after its release...

I'm not a fan of the MDD models because I find the power supplies to be a bit cantankerous.

With that said, there is a fair bit to like about them. The higher end models had the fastest FSB of any G4-based desktop. Combined with the dual 1.25ghz processor(which has an L3 cache-something that some of the lower end MDDs lacked), the ability to take 2gb of RAM(DA and Quicksilvers reduced that to 1.5gb), and the ability to take 4 hard drives they could make very formidable systems. Even though the dual 1.42 wasn't offered in a model capable booting into OS 9, it could easily be swapped in to make a killer OS 9 machine(if you do this, just make sure you get the copper heatsinks that go with the dual 1.42-it's the hottest running G4 processor Apple put in a desktop, and needs this heatsink to avoid cooking itself). Of course, again, OS 9 itself doesn't benefit from dual processors, although some applications can(Photoshop 7 comes mind). OS X-particularly in later versions-really does benefit from dual processors as it will spread tasks across both cores even when not running a multi-threaded application.

I think that the "wind tunnel" think is a bit overblown(no pun intended). The CPU fan on the Quicksilver towers makes quite a racket, and doesn't even cool them that much-at least not on the dual processor models. IMO, the MDD got it right by putting the 120mm main case fan right in line with the heatsink-or at least that's where it is when the case is closed. The case architecture really didn't change appreciably from the B&W G3 up through the Quicksilver, and I think that the hottest Quicksilvers really pushed the thermal limits of the design. The MDD was completely redesigned the case inside, and IMO Apple got a lot of things right with it at least as far as keeping it cool.

All of that said, my most used G4 is a factory dual 1ghz Quicksilver. It's faster than my dual 1ghz MDD(thanks to the L3 cache, which the dual 1ghz MDD lacks), but in my judgement is also louder. Unfortunately, I've pretty much killed its ability to do anything productive in OS 9 by chasing maximum OS X productivity. It's had a bit of a revolving door of video cards, but I've long since passed anything that is supported in OS 9. I'm currently running a Radeon 9600 Pro PC & Mac edition, but will be switching it out for a flashed ATI FireXL G3(now a Mac Radeon X800 XT) if I can ever get it to play nice with the Quicksilver. Core Image support(which the 9600 offers, as do all the other cards I've been chasing) makes a big difference in OS X Tiger and a huge difference in OS X Leopard, but again comes at a cost of any real support under OS 9.

I'm probably in the next few weeks going to be buying a Gigadesigns dual 1.8 to put in one of my Quicksilvers. The seller-a regular over at Macrumors-is fed up with it and made me a good deal on it although sent me a long list of all the problems it has before we even talked price. Even so, I'm going to go for it, and see if I can make something of it in one of my spare Quicksilvers.