If you run it with the GUI it runs with 256MB from my understanding (Bukkit has no GUI, so no worries here), Notch recommends 1024M of RAM, however it is not necessary.
To start a server with 4GB of RAM, you should use this command:
/usr/bin/java -Xincgc -Xmx4096M -jar craftbukkit-0.0.1-SNAPSHOT.jar
Take note this is on Linux, windows I am not sure of as I do not use Windows on any of my computers/servers. By using -Xincgc instead of -Xms4096M, means it will go lower to a point handled by the CPU, therefore you have no control over the minimum, which is a good way of having a powerful and efficient server.