Alestic and Canonical have released new Ubuntu AMIs for EC2 - the EBS version in the eu-west-1 region has AMI ID "ami-38bf954c", and the source is "099720109477/ebs/ubuntu-images/ubuntu-lucid-10.04-i386-server-20100827".
Ubuntu images support CloudInit, which runs scripts on startup to allow you to configure the server (set up ssh keys, update the repos etc). There's a load of different ways to specify what should get run (see https://help.ubuntu.com/community/CloudInit for full details).
One of the simplest is just to give it a script in the User Data, like this:
#!/bin/sh echo "Hello World. The time is now $(date -R)!" | tee /root/output.txt EOF
It runs as the root user, so you can do pretty much anything you want to configure the box.