Optimizing your system for interactive 3D applications can be tricky. There's no way to say for certain that *this* or *that* is limiting your performance, since everything is interconnected. A slow CPU can make a fast GPU worthless, and a fast CPU can still be throttled by a slow CPU.
Memory is the only thing that's easy to measure. Fire up Task Manager and see what it says. If you're using less RAM than you have installed, you probably don't need more.
One test you can try is to check your CPU utilization with the program running. I'm not saying this is a perfect benchmark, but on a properly written program, the CPU will surrender cycles back to the system when the video card is doing its thing. On my system, I think my CPU is only running at around 30-40%, which means that a video card might help me.
It sounds like your entire system is a little older, so you really should consider either a major upgrade or a new computer. If you don't want to buy a whole new computer, here's the upgrade path that'll give you the most bang for the buck (in this order!) In short, don't expect to do a $100 upgrade at this point. I'd set aside at least $400 to make the jump to the next level. If you can't spend that much, then wait until you can.
There's one caveat with this list: if you already have a motherboard with PCI-E on it, then consider the new video card first. You can do the rest later.
You reall need a new Motherboard, CPU, RAM, and video card. Since every bus technology has changed since your P4 was hot, this has got to be the place to start. You need Serial-ATA, PCI-Express, and DDR-3 to get to the next generation.
Get the fastest dual-core (or more) CPU that you can afford, after pricing the other stuff
Get 2GB of fast RAM.
Get a video card that's at least equivalent to the GeForce 7600, 8600, or 9600.
This little site is a great tool for comparing video cards. You'll notice that the 7600, 8600, and 9600 have about the same raw performance. The differences are actually pretty subtle, but the newer cards can handle more and better shaders - making your image look better on programs that handle it. Whether you get ATI or nVidia is completely up to you, just make sure you at least match the performance of the 7600. That's as slow as I'd want to get on a modern PC (you can and probably should do better.) If you spend $200 on a video card, you're probably in right about the right performance range.
So right there, you've spent about $500 or so. That's the hard-core stuff that makes up the meat of any upgrade. What may get you in trouble at this point is that new motherboards are starting to ship with only one IDE connector; this is because all the new, large hard drives are SATA, and the old fashioned IDE port is only there to support a CD or DVD drive.
Hard drives can be had from $100-200, depending on capacity. You won't get much of a performance boost with a new drive, except for while the game is loading. I do see quite a bit of difference between the computer with the old hard drive and the new one that's booting off of a nice shiny SATA drive.
The other decision is whether you should load 64-bit Vista or 32-bit Windows XP (don't bother with 64-bit XP) on your new system. I have experience with both now, and I don't think you will really have much trouble with either, as long as you have new hardware. I have Vista and XP on my PC, and I don't really see any major peroformance difference between the two. Vista still has some annoying glitches, but so did XP. If you decide to go with Vista, make sure you can track down Vista drivers for any older hardware before you even try a Vista install. Otherwise, go ahead and stick with Windows XP.