Memory alone is not everything. It also depends on what the GPU can handle and what the game was programmed for. But, for today's games, you need at LEAST 512mb. 1gb is even better.
But, as I stated, it's more than just memory. For example, a game could be written that expects the card to have a model shader that is version 2.0. Therefore, regardless of memory, you have to make sure that the card you purchase has at least a version 2.0 model shader in it (this will be listed on the box of the card).
Where memory does help is the more you have, the more detail you can boost up in the graphics settings.
Of course, then it comes down to ATI or nVidia. If you have games that use PhysX and you want it enabled, then you go nVidia. Again, it comes down to choices.
If you wanted DirectX 11, you went ATI, although that is about to change with nVidia releasing the GTX 480. Now, you can have DX11 and PhysX if you so desire.
The best thing to do is research. Look at what each card gives you and read reviews on them. Tom's Hardware has PLENTY of benchmarks and reviews on the various video cards out there. You have to decide how much are you willing to spend, how long do you expect to keep the card before upgrading again and what features do you want.
There really is no one true way of deciding what you want. For example, many told me I should skip getting the 5750 and get a 5770 for the extra $20. My problem was, I budget for my PC and all I had left was the 5750. Now, I was also upgrading from an ATI HD 3870, so my upgrade was actually a vast improvement over what I had, especially because it gave me access to DirectX 11. My factors were I needed a card that could still give me decent frame rates plus could last for a while and still play the latest games but all at an affordable price. For me, it had to be less than $180 and I couldn't find any 5770s at that price (even though many told me they are out there). I eventually found the 5750 for $130 at TigerDirect with free shipping, so that's what I went with. Again, it was my personal choices that made me decide on that card. For everyone else, it would more than likely be different.
Just research, read and learn. It will definitely make you understand better what your choices are and you know that you made the right choice in the end based on what your needs were.
Memory is important for speed but the features are ultimatly the important aspect.
Newer cards are much faster and to a degree do not alway require maximum memory in order to queue commands.
Since the video is what you will notice the most it is important to get the best that you can while looking at possible future requirements.
Even if you upgrade the computer you will still have the option to use the video card for some time.