Since the backup-manager versions in Debian and Ubuntu are little bit outdated, I would recommend installing the 0.7.5 Release from the Website. While the installation of backup-manager is painless, getting the s3 part running a little bit tricky (and undocumented).
The s3 part of backup-manager is based on the Net::Amazon::S3 perl module and this needs the XML::LibXML::XPathContext module, which is, as far as I can see, not included in one of the libxml-*-perl packages in Debian or Ubuntu.
So, this procedure gives you all the needed dependencies:
sudo apt-get install libperl6-slurp-perl libxml2-dev sudo cpan XML::LibXML sudo cpan Net::Amazon::S3
Update: (14.06.07) Ubuntu feisty now contains the 7.5.3 version of backup-manager.