I'm amazed at the performance and efficiency of web2py framework. Most python frameworks are memory hogs and I wouldn't run the application in anything under 512M of memory. But web2py seems very tight and efficient and quite capable to run in some of the smaller footprints offered by some cloud providers.
I personally use and of course recommend Rackspace Cloud (aff.) where the smallest instance is 256M of RAM with 10G of disk space with larger offerings that give you options to expand this modest VM into a large scale cloud server that rivals a dedicated server
Even with the growth options Rackspace offers, you want to keep your installation tight and to a minimum. There are many Linux flavors, but Ubunto is about the simplest to use for managing your server and like most cloud providers, Rackspace has the latest version LTS 10.04 pre-built and ready to deploy for you.
You probably could get by with a simple Linux-Apache-Python (LAP) install since web2py uses sqlite3 as the database for the model, but a LAMP (+mysql/postgresql) will fit into the reduced memory size.
The following script will install everything you need
wget web2py.googlecode.com/hg/scripts/setup-web2py-ubuntu.sh
chmod +x setup-web2py-ubuntu.sh
./setup-web2py-ubuntu.sh
This will put your web2py install in /home/www-data/web2py.
You may have to run web2py directly from the command line once so that the remainder of the directories and files are created. This is not done for you in the setup script since it basically configures Apache and starts up web2py via the wsgi.
Just run:
python web2py.py -a "hello"
to create a dummy application and your web2py server running on Ubuntu should be ready to go.