All notes mysteriously disappeared across all synced devices. Can I recover?
I have three questions here and I was able to figure out the two, with a guess for the first.
What could have happened here such that all notes were deleted?
I don't know exactly, but my guess is that the notes database was corrupted somehow. Most likely, the corruption happened on my phone (since I upgraded an OS patch two days ago). When my iPhone synced its corrupted database with iCloud, all notes there were deleted too. And then the corruption was passed on to my laptop. This is just a guess, though.
However, it seems like others have had this problem, too.
How can I prevent this from happening in the future?
The key thing to remember is that syncing is not a backup. If you sync corrupted or deleted data, then everything is corrupted or deleted. The most important thing to do is make sure you have backups of all your important data AND check to make sure that your backups are actually working properly.
In my case, the backup software on my laptop was not backing up anything in my ~/Library directory (which is where the notes archives are stored) unless I went in and changed some arcane settings. After this was done, I have this folder backing up.
I also installed Exporter from the app store which allows you to export your notes to text. This will be another stopgap for me if this ever happens again.
Is there any way of recovering these notes now? (For example, might they be in my iPhone backup?)
It turns out that yes, these notes were being backed up on my phone, but it was more complicated than just applying this backup to get the notes back. If I didn't do anything else, once the phone starts syncing with iCloud, all the backedup notes were immediately deleted because the synced notes on iCloud is &quot;newer&quot; (ie- the database corruption happened after the backup, so the corruption overwrote the notes).
What I needed to do was:

reinstate the backup
immediately put my phone into airplane mode so no syncing happened
open the notes app
move all notes to a non-synced folder outside of iCloud
take phone out of airplane mode
let the sync complete (ie- the local phone's synced folder and iCloud are now both without any notes, but the non-synced folder has all notes).
Move the notes back to the iCloud folder.
Allow sync to happen as normal.

This solved the problem.