Ghetto solution is to find a service that will allow you to rsync files to them and take care of offsite backups etc themselves. Once you have done that it's a simple case of setting up mysqldump to create timestamped .sql files and setting that up on a cron job to rsync to the remote server via SSH (you need to generate a key pair and copy the public key to the other end).
If you are using characters from weird character sets you definitely want to make sure all of your unicode settings are correct which may take some trial and error and I've never entirely trusted mysql in this regard.
If you are paranoid you should have a separate job that automatically downloads and restores your backups after a period of time and runs a few test queries on the data. Of course the hard part is knowing what the results of these queries should be.
Of course the problem here is that this will chew up increasing amounts of your remote storage over time, so it depends if you can afford to delete backups of over a certain age.
You can also enable binary logging in mysqld and do incremental backups by writing the binary log to the remote host at certain intervals (I think this only works properly with InnoDB databases), though I have no practical experience doing this because frankly I've never needed to. Nightly dumps were always good enough so my boss wouldn't want me spending any more time on it.
That's the crux of the problem with working for a non tech company, most of the time once the solution is "ok" it's time to move onto something else so you never get a chance to really kick ass which is what you need to do to justify a high rate.
These are really commodity skills though, you could have figured all of this out yourself by reading a few blogs (that's basically all I did). Alternatively if you had posted "Mysql backup solution needed" on eLance you would have probably had at least 20 offers to do the whole thing for $20 or so.