right now, except for FarCry from Ubisoft, games only require 128 MB. In the near future, they will use the 256 MB of video cards if it is available. Before you go and buy a 256 M video cards, go and check some reviews from toms hardware or anandtech. Some companies boast 256 M but what they did was use the cheapest slowest memory available just to boost their sale. Go for good reliable companies ( I prefer brand names such as ATI made cards) but saphire also offer good quality.
I myself have the 128 MB ATI 9800 PRO but it is coupled with 1 G of RAM. The new generation cards are slowly coming out which means that older cards (i.e. 9800 pro, xt etc...) prices will come down in the next few weeks.
The best advice I can give you is shop before you buy and read reviews on the cards you want. Don't buy a card from what is written on the box.
Give us your computer specs and we'll be able to help you more as not all cards are compatible with all mother boards (specially older ones).
My gaming machine:
P4 2.8 GHz
2 X 512 MHz PC3200 in dual DDR mode
Intel D865PERL MOBO
integrated 6.1 MAX audio
Logitech duo MX mouse and KB
ATI RADEON 9800 PRO