At the present time you have 3 choices for affordable (keyword there) multi-core processors, that being dual-core, triple-core and quad-core.
If you’re going Intel you can do duals and quads. With AMD you have duals, triples and quads.
No matter what brand you go with, multi-core (sometimes known as many-core) is the way to go. They run circles around single-core CPUs, and if you’re not running one, you should, plain and simple.
As of now multi-core is cheap to run, and the motherboards that support them are also cheap to own and run.
On the Intel side, a retail-boxed (meaning it includes the fan and all that stuff) dual-core non-Celeron is $69.
On the AMD side, a retail-boxed dual-core is $45. True to tradition, when going AMD you do save money over Intel – both on the CPU and the motherboard.
And by the way, that AMD I linked is only a 45-watt. It’s cool, as in literally cool-running compared to the Intel which is a 65-watt.
The choice of which company to go with is ultimately your decision. At the present time I’m running an Intel dual-core and yeah, it’s awesome. But I’m quite sure AMD duals are just as nice.
For those of you out there wondering whether Windows XP has any issues with multi-core, the answer is no. XP has absolutely no issues with a multi-core processor. In fact, when I first used a multi-core with XP I was surprised it didn’t have any issues whatsoever. It just booted and ran exactly like it was supposed to do the first time and every time after that.
Multi-core is not expensive, and said honestly it’s the best possible upgrade you could do. Once you go multi, you never, repeat, never go back. 
Let me say it another way. Have you ever dabbled in overclocking or the like with single-core CPUs? You don’t even need to bother when running multi-core. They’re plenty fast enough right out of the box. Yes, some super-gamer types may argue to the contrary, but for the rest of us, multi-core as-is is more than enough.
If you have an older computer with a single-core processor then you’ll probably need to upgrade the motherboard as well as the CPU to go multi-core. If it’s a particularly old computer then I’d suggest simply buying a new one with a multi-cored processor fitted from the word go.
What about upgrading your existing processor on your existing motherboard? It’s a possibility; but you’d have to take into account things such as motherboard’s capability, as well as its processor socket:
For instance; an AMD socket AM2 CPU will fit into a socket AM2+ motherboard; but not vice-versa: Therefore if your existing processor is, for example, a socket AM2 Athlon 64 single-cored device, which you want to upgrade; then, providing that your motherboard is capable of running a dual-cored CPU, (CPU=processor.) you’ll have no problems in replacing your existing CPU with a socket AM2 Athlon 64×2 dual-cored processor, providing that the motherboard’s chipset is capable of supporting the operating frequency of the new component. You’ll probably need to run a maintenance-reinstall of your operating system though; as a system configured for a single-cored processor probably won’t instantly recognize that the new processor has 2 cores, and will only run 1 of the cores unless it’s reconfigured.
Further to the above; if you want to upgrade from a single-core Athlon 64 to a quad-core Phenom, which is socket AM2+, you’ll need to upgrade the motherboard as well as the CPU, as a socket AM2+ CPU simply won’t fit into an AM2 socket. Also the motherboard with an AM2 socket probably won’t be capable of supporting more than a dual-core CPU…
There’s a lot to consider; in addition to simply swapping the processor. If in doubt I suggest a motherboard and processor upgrade would be the best option – Which will once again maybe require you to perform a maintenance-reinstall if using the same hard-drive.
(Don’t forget to install, and upgrade afterwards if possible, the new motherboard’s drivers.)
Best of all IMO would be a total-rebuild (Strip everything out of the case and renew it with new compatible parts, or ditch your old machine and build a new one.); after which you can install any really important files that you want to keep to your new hard-drive from a backup you took of your old system.
All AM2, AM2+ and AM3 processors will fit on a AM2 motherboard. Whether the AM2 motherboard will support the newer processors is up to the motherboard manufacturer. Check the motherboard manufacturer’s CPU support page and update the bios before you upgrade.