With the new version of OS X (Leopard) Apple has included some great functionality in Time Machine. Your Mac will automatically backup to an external drive every hour. It includes the ability to recover deleted files in a timeline.
Amazon's S3 is an online storage solution; you pay for only what you use ($0.15/GB/month, plus some transfer costs). I wrote a simple step-by-step guide to setting you a Mac to sync with Amazon S3; here's the executive summary version: