The easiest method involves starting from an existing public AMI and modifying it according to your requirements. This is applicable for both Amazon EBS-backed and Amazon S3-backed AMIs, and is described in Starting with an Existing AMI.
Another approach is to build a fresh installation either on a stand-alone machine or on an empty file system mounted by loopback. This is only applicable for AMIs backed by Amazon S3 and entails building an operating system installation from scratch.
That sounds like all future AMIs have to be based on existing ones, but that would be very limited. Do I understand this correctly or are there any other ways of creating AMIs not based on existing ones? I would be interested in creating ubuntu AMIs.