512MB will be fine, if you only search the web and don't mind huge swap files. I haven't been messing around with much lately that requires gobs of memory, but 512MB under Tiger just isn't cutting it for me. It usually takes less than a week for me to accumulate 1GB in swap files with 500,000+ pageouts—and that's from surfing the web & e-mail, running Word, viewing QT movies, etc.
Even with Panther I would suggest 1GB for moderate use is probably a good number. 512MB should be regarded as the absolute minimum, IMO. Definitely so with Tiger.