if possible, i would return the machine or sell it. the best choice for a new computer is a standard PC, not a mass-produced name-brand OEM rig. OEM vendors such as gateway, dell, sony, and HP use specialized parts that are all too often incoherent with industry standards. consequently, attempting to interchange your stock parts (namely the power supply) with normal parts may result in failure.
if your gateway happens to be compatible with a standard power supply, i recommend the antec smartpower 2.0 SP-500. it is a 500W ATX supply with modular cabling and thermally controlled fans. it's a reliable, quiet, and powerful supply that costs $70 (USD) and is available at most local shops and online retailers.
as for video cards, i recommend that you get an nvidia-based card, 7600GT or higher. BFG, asus, gigabyte, msi, and XFX are all good brands that have competitively priced models. i reccomend the asus 7600GT model, it costs $140 (USD) and is a solid choice.
getting a decent card and power supply as mentioned will cost you about $200 (USD), or a bit more depending on your choices.
remember, because you have a new gateway, that even opening the case may void the warranty, and changing parts definitely voids the warranty.