How to create EBS based EC2 AMI from scratch?

http://www.elastician.com/2009/12/creating-ebs-backed-ami-from-s3-backed.html

For Ubuntu in particular you could try these instructions http://alestic.com/2010/01/vmbuilder-ebs-boot-ami.

Here's a script I use to build a Git/gitolite server AMI using the downloadable Ubuntu server file system as a base:

https://github.com/alestic/alestic-git/blob/master/bin/alestic-git-build-ami

Here's more info about the Alestic Git server project for EC2:

http://alestic.com/alestic-git/

The vmbuilder-ebs-boot-ami article I wrote on Alestic.com (linked to in the answer by Bribles) is now outdated.