Knife and Chef: http://www.opscode.com/chef

We start with a base image and then use puppet to manage anything that needs to be installed/setup.

I use a custom AMI. I started with a base image a long time ago. Since then I have been upgrading and tweaking. There are several tutorials on creating the image. API tools are available for the whole process if you are on an instance-store image. It creates an image of the instance filesystem in /mnt and then breaks it into chunks to upload to s3 with a manifest and registers the manifest as a new private ami.

If you're using Ubuntu, they have a tool for creating new EC2 images called python-vm-builder-ec2.

yes, that is what i've done, or rather just log in, set things up, and then save a snapshot, repeat as needed. not sure this will speed things up in general as far as iterations, but may save the $0.10 you may spend setting up a workable vm.