What's the best way to back up Amazon EC2 machines with Bacula? Currently it seems not possible to use S3, is that correct? Could it just be done with EBS?
It should be possible to back up Amazon EC2 machines to S3 with Bacula, as that is possible for non-EC2 machines. That is how I do some backups. Though, 'possible' doesn't mean 'directly supported by Bacula' or even 'easy'.
In my case configuring Bacula with S3 storage meant using both 's3cmd' utility and 's3fs' user-space file system and configuring Bacula to do 'DVD' backup with specially crafted 'part write' and 'mount' scripts. I have encountered a lot of failures until I tuned the scripts so everything worked reliably.
With EBS on EC2 things should be much easier, as EBS can be treated as a regular disk. Just use the instructions for backing up to disks.
I guess that with EC2 your biggest problem should be how to maintain a reliable Bacula catalog. EC2 machines can be restarted anytime and databases, like Bacula catalog do not like that.