Don't buy the memory card with the camera a smost retailers mark up memory cards too much, buy it seperate but buy one. I've stuck a 2G in ours.
You will find plenty of different memory card formats, some standard and some now.
Most popular is SD, then you see CF in some higher end cameras because it can still be faster, then every now and then you kight find one that uses XD thought I thought that format had been discontinued and then you have the Sony which use memory stick.
SD and CF you will find plenty of vendors and sellers, the less popular like XD you may have to hunt for then with Sony you have a half dozen different variations of the Memory Stick that you have to check for compatibilty and you will pay more for since any other company that wants to make a memory stick has to license the format from Sony.