So you have 2x512MB and you're looking to upgrade to 2GB total?
Your options are
1) Get another 2x512MB and run 4x512MB. Running four sticks is said to reduce stability, but this is mostly an issue with crappy motherboards and overclocked systems. Your memory is only as stable as the weakest chip and the board's ability to make them get along, so this is a real issue to people pushing their memory speed/timings. Running four sticks also forces your system into 2T command rate, and although there's a nice thread proving saying it's not that big a deal, it's something to avoid if you can.
2) Get a single 1GB stick, and then you'd be running three sticks of mixed memory. Does that even work in dual channel on an A64 like it does on the NF2 chipsets? Even if it does work, it's not better than the first choice, so you'd be better off saving some money and staying with 2x512MB (since it's cheaper than 1x1GB)
3) Sell your 2x512MB and get 2x1GB. This is the best choice if it's not too much of a hassle.
If you're not overclocking or anything, though, and you have two empty slots, there's really nothing wrong with just getting another $80 2x512 kit. It's $20 less than a 1GB stick, and you're not going to notice the difference. I'm using a 1GB stick so I can upgrade to two 1GB sticks later, but that's really just because I'm a big geek and worry about a lot of stupid little details that don't make much difference (just like 90% of the people on here which is why most people will tell you to ditch your old memory). In reality it's no big deal.