Just upgraded from PIII 667 128->256 -> Athlon XP 1700+ 512 DDR
The difference one notices depends on workload and system. If you're multi-tasking like crazy and have 64MB you're definitely going to notice the difference. If you're like amish and don't multi-task, well 256 may be good enough for you, but imagine what you COULD be doing, you never know, you may get hooked.
Personally speaking, I multitask a great deal.. multiple IE windows, icq, aim, etc. I noticed a small difference upgrading memory so definitely take memory on a case by case basis. If all he's going to be doing is gaming, then NO, 512 is NOT NECESSARY. but it doesn't HURT. Except in the pocketbook. Wait until prices come back down to earth.