First thing to do is setup Ubuntu's Apache to correctly use mod_rewrite.
Enable the module: sudo a2enmod rewrite.
Use your favourite text editor to edit /etc/apache2/sites-available/default. Change line 12 from "AllowOveride None" to "AllowOveride All"
Reload the webserver with sudo /etc/init.d/apache2 force-reload
Check that Apache has loaded the module: apache2 -M
Optionally you could check mod_rewrite is working by following the steps here

I'll assume you're starting from scratch with Akelos. Download akelos-dev_preview.tar.gz from www.akelos.org. Place the file in your home directory.

Unpack the archive with tar xzvf akelos-dev_preview.tar.gz
Rename your new directory: mv akelos_framework akelos
Create a softlink to this directory from /var/www: sudo ln -s /home/dan/akelos /var/www/akelos (use your own home directory name of course)

Now if you go to http://localhost/akelos you'll get the 'Welcome aboard' screen.

Before you click through the screens, create your 3 databases in MySQL (Quickly: do mysql -u root -p, enter your password, run the create database SQL command to create akelos, akelos_dev and akelos_tests databases, exit) and give Apache write access to the akelos directory with sudo chgrp www-data /home/dan/akelos -R and sudo chmod g+w /home/dan/akelos -R

Now go through the setup screens at http://localhost/akelos. Did you get a 500 Internal Server Error after the language select screen? If so edit .htaccess in the akelos directory. Change the line RewriteBase akelos to RewriteBase /akelos/public. Refresh your browser and you'll have the Welcome aboard screen.

Make the same change to the .htaccess file in akelos/public: change RewriteBase akelos to RewriteBase /akelos/public

Now - from inside your akelos directory - run ./script/generate scaffold Post

Almost there... if you go to http://localhost/akelos/public/post you'll get a series of warnings. I think this is because somewhere along the line akelos has changed some permissions. So rerun sudo chgrp www-data /home/dan/akelos -R and sudo chmod g+w /home/dan/akelos -R. Now try again and you should have your Create new Post screen. Hooray!

I hope this long-winded explanation is useful to someone. In summary there were three problems to solve: getting mod_rewrite working in Ubuntu's Apache setup, pointing RewriteBase to the public folder and making sure Apache had write access to all Akelos files and directories.

Now to try creating a post...