Sorry, no they do suggest buying 1x1GB and keeping the 256MB in, not getting 2x512MB.
Yeah, I noticed that bit - I was agreeing with them

I just seem to remember being told once that you had to have the same in both slots. Just wanted to check before I ordered it.
Not really. If you have 2 different speeds of RAM in then the slowest speed (not talking about the capacity of the RAM here) is what you'll get. But you can mix and match so long as it's all compatible with your PC, and you can leave slots empty if you didn't have enough sticks to fill them, though it's better to fill them all if you can.