It depends what you use your card for. If you only do 2D stuff, 8 MB is more than enough.
If you use your card for 3D gaming it depends on what games you play. The older games tend to use smaller textures so 16 MB boards are just fine for them. For the newer games you need more video RAM, and if you're running with texture compression turned off and/or high detail/high res settings, you'll need even more memory.
32 MB is the standard these days and 64 MB is considered high-end.