Try Crucial. Run the System SCanner and it will list the options for your PC and tell you what is fitted at the moment.
Yes you need SDRAM.
Yes you can buy RAM with a higher speed (higher than 333MHz) but it may alny run at the lower speed governed by your motherboard.
Yes you can buy a stick at a time and mix 256MB and 512 MB (Note some PCs require matched pairs of RAM but think Crucial will indicate this if it applies)
With RAM "cheapest" isn't always best, Crucial are good quality and service and competitive price. Kingston have good reputation also.