Depends on your mobo. If you have an Intel CPU then it doesn't really matter.
If you have an AMD cpu then you want two matched sticks to get the performance benefit of dual memory mode (dual memory only works with two matching sticks in the proper sockets - check your manual).
Also, are you a gamer, or a desktop user? If you're a desktop user and you're not a power user or leave a lot of windows open at the same time AND you don't use a major bloatware anti-virus app like Norton Internet Security, a total of 512MB is all you really need and 768 (512 + you existing 256) will be even better. You're definately going to see a big performance improvement over 256Mb.
If you're a serious gamer (which I doubt if you only have 256Mb installed right now) then you really want to have at least 1Gb installed.
Either way, you don't want to mix sticks with different timings. Modern mobos are rather fussy about timing.
If this is an OEM system (Dell, HP, Compaq, whatever) then I would highly recommend you order your extra memory from Crucial.com to be certain that the memory is matched to the computer. Crucial has an database on their website and you enter the make and model and it tells you what the right match is and you can order it direct. I order memory for my clients from them so I can always be assured of no problems.
If this was a custom build you can also order from Crucial, or you can order some other memory if you prefer. You can save some money, but personally I'd rather order from Crucial and get memory that works without the headache of tweaking it.
Hope this helps...