So I have a few specifics here that might make this harder than it would otherwise be:

1) SQL Server running on Linux (Ubuntu) in an Azure VM
2) Backing up to Azure blob storage
3) Using the amazing Hallengren helper scripts for backups
4) Scheduling these from SQL Agent jobs (the ones that get created when you run the Hallengren install script)

So here is how to make it work.

Azure Storage

Nothing too funky here, just create a normal storage v2 account and make it public (the container will be private). I don't know if the problems I had previously on private storage accounts were because they were private or because of something else that I have now fixed.

Create a Shared Access Signature for your SQL server to access the account with. These are nice because they are time-limited and affect the scope of what the token can perform. I only allowed blob access and removed the delete permission. You can optionally lock this down to an IP address. I gave mine 1 year but remember that you need a regular job to rotate these and if the access key is changed, these will stop working.

Copy the SAS WITHOUT the leading ? character.

Create a private container to store your backups in in the blob service section of the blade.

SQL Server Prep

Install the Hallengren scripts. This will create stored procs and some SQL agent jobs (if you haven't already, you might need to enable this on Linux). By default, they are installed into master.

Create a credential for use with an SAS by following this. Note that the following code will ONLY work for SAS. If you are using the access key, see the alternate instructions in the linked article.

(SELECT * FROM sys.credentials  
WHERE name = '') 
   SECRET = ''; 

Note that the identity must equal "SHARED ACCESS SIGNATURE", you cannot change that part. Remember to paste the SAS token WITHOUT the leading ? character.

Calling the Backup Script

The SQL Agent jobs created by the Hallengren script are designed for local backup to a directory. Instead, you should change the SQL that is called from the job to look like the following:

 EXECUTE [dbo].[DatabaseBackup]
@Databases = 'USER_DATABASES',
@URL = '',
@BackupType = 'FULL',
@Compress = 'N',
@Verify = 'Y'

But obviously check that the individual settings are correct for your job (full, partial etc). Note that there is an issue with @Compress in that it only works for certain versions of SQL Server and it was not supported on mine. You can always try Compress='Y' and you will simply get an error if it is not supported.

Do NOT use the @Credential parameter when using SAS, it will automatically find the correct credential from the URL.

When you run the script manually, you should see some output including any error messages and the actual command that is generated by the script. This should be enough to work out any problems with the script and there are certain limits like max database size and other options that are not supported when backing up to blob storage.