The important thing to note here is that you cannot add a VM to an availability set AFTER the VM is created. You have to do it during creation of the VM. The only way to fix this if you forget is to delete the VM and keep the storage and recreate it but attach the retained storage VHD. Kind of a bummer. Here's how you pull that off:
Add this line:
$availabilitySet = New-AzureAvailabilitySet –Name $avName –ResourceGroupName $rgName
Change this line:
$vm = New-AzureVMConfig -VMName $vmName -VMSize $vmSize -AvailabilitySetId $availabilitySet.Id
Thanks to my colleague Roelf Zomerman for the tip!
Note (and updated my blog post) - change everything to "AzureRM" commands as appropriate to deploy to Resource Manager better