Yes, upgrading a video card is quite easy. I upgraded mine last week; I did almost exactly what David said. I uninstalled my old graphics driver, installed the new graphics driver, shut down the computer, swapped out the graphics card (while wearing an anti-static wrist strap), and powered up the computer again. When Windows XP popped up the driver install window, I directed to the location where I had installed the drivers, and then the installation was finished except for setting the color depth and resolution to where I wanted them.
BTW, what video card are you getting? I got a card based on the GeForce FX5200 chipset with 128 MB of RAM, and it really improved my performance (old card was ATI Rage 128 Pro with 32MB of RAM)!