I have a little bit more information here.
I suspected that GCM might be the culprit, and it seems to be the case.
A brand new Cyanogenmod 12.1 or 13 does not result in notifications with Firefox Nightly.
A brand new Cyanogenmod 12.1 or 13 with Open GApps Pico or better does result in notifications in Firefox Nightly.
As such, I think the First post should include the information that Open GApps Pico is a requirement for Android+Firefox.
My colleague with Chrome still cannot get notifications with Chrome, so I will debug when I get a hold of his device again.