Either really - I would buy a new 512Mb module and run that on its own.
You can leave your current 256 Mb module in place - it WILL make a difference but you probably won't notice much difference over and above the new 512Mb !
It may depend on whether your new module is the same make as the existing one, as occasionally problems can occur with memory of different makes that are "unmatched", causing crashes and other "glitches" so I'd try it - see how it goes - if it all runs fine with both modules then great, otherwise you could always sell the old one on E-Bay for a few quid to offset some of the cost of the new one
Coconutty