I have a few things to say about this.
First and Foremost, I want to re-iterate what Vger said about managed servers. If you purchase an unmanaged VPS, you will need to know basically how to install a fully functional (and secure) linux webserver. If you have not done this before, definitely definitely definitely get a Managed VPS...preferably one with cpanel.
Cpanel is a great / robust interface for managing a server.
Secondly, Most VPS these days are 'burst-able'. They will have two numbers...for example it might be a 256m vps, burstable to 1024m. This means you will NEVER have BELOW 256m of ram....and you get to fight the other vps' on the server for the remaining 756 megs or so.
Thirdly, 256m of ram is MORE then enough to run a zencart(and much faster then shared too!). The key here is in how you configure your httpd.conf in apache. Your system, once installed, will take a certain amount of memory to keep it's day to day services running. This is likely to be about 10-60megs for operating system overhead.
What really takes up memory past that is apache. Any open web connection may take anywhere from between 5 -> 20 megs of server memory. You can check on this with the 'top' command in linux. Apache by default accepts up to 256 connections at one time. Obviously if you accept 256 connections at a cost of 5-20 megs, it's going to drop your VPS down to a crippling speed. At anyrate...if you set your apache MaxClients directive to like 30 or 40, a 256 vps can TOTALLY handle traffic.
Mine right now has 8 sites on it, and takes about 4000-5000 people a day without a hitch.