For the Radeon 9600 XT, $250 should be about the regular price, rather than a sale price. I bought a Sapphire card (from
Genitech) because it had 256MB RAM for the same price as most other 128MB cards (though the core/memory clock speeds are slightly lower).
Intel's
D845GRG product description says it has an AGP slot (4X, 1.5V), which is compatible with the
Radeon 9600 series. Gateway may have a version of the board without an AGP slot, but I would expect the model number to be different in that case.
You definitely need a new power supply if you are going to be adding a graphics card (or much of anything else). Check the case and see if there is physical room for a power supply about time and a half or twice the size of the one in there now (I'm pretty sure it is just a baby PS). If there isn't, you would have to move everything to a new case. A 300/350W power supply would be about $50-70, while a case and power supply would be range from $50 to about $160. A cheap case is OK, but you don't want to skimp too much on a power supply.