I found the following site regarding your computer. Although it says "Add-in card slots: One PCI Express® x 16 slot," it also has a footnote that says specifications may vary in this series:
http://support.gateway.com/s/desktop/2011/gateway/dx4850/DX4850sp5.shtml
But if you do actually have that slot available, you should be able to buy whatever video card you want.
Now, how to decide? Typically you can spend the most money you can afford, but then that side-steps the issue of what is the best value. To find the best value, you could analyze cost/performance ratios, but should consider how you find a video card valuable?
If you know nothing about video cards to the point where you aren't yet ready to appreciate the benefits of the very expensive cards, it might make sense to start with something more affordable and mainstream, because you could buy it cheap and re-sell it for close to what you paid. Perhaps buy a used card off craigslist?
Anyway, there are usually sweet spots of different price points, where a particular card might be the best value at that price point. As an example, I think Nvidia just released a new card recently at the $250 price point that seems to beat it's previous cards on price/performance, making it a good buy. But can you handle all that performance, or appreciate it? Maybe a $150 card would be just as appreciated by you, and keep you very happy for years, such as a used AMD 7850 card (or even new, sometimes they have rebate specials that drop their new prices near that low).