Why isn't Hibernate in Ubuntu 16.04 working and how to fix it?

This is probably due to changes & regressions introduced in the 4.4.0 kernel such as this with Ubuntu 16.04, but I do have a workaround for 4.4.0:

I first added my swap partition to grub, rebooted, and there was no change. Next I installed the Ubuntu kernel packages with TuxOnIce stable and the option to hibernate appeared, but that failed. I later I installed the package hibernate which uses uswsusp for suspending to disk & ram and that worked. Below are the exact steps to achieve this:

1. Double check if your swap partition/file(s) are setup correctly in /etc/default/grub; you can do so by checking the location with either cat /proc/swaps or swapon -s.

   Better yet, find out the UUID or label of the swap partition/files(s) and use that:

   tail -n -9 /proc/swaps | cut -d ' ' -f 1 | xargs sudo blkid
   

2. Edit /etc/default/grub by finding the line with GRUB_CMDLINE_LINUX_DEFAULT=, add your swap device(s), and save. To enter the UUID, prefix it with UUID= or /dev/by-uuid/.

3. Save changes to GRUB:

   sudo update-grub
   

4. Add the TuxOnIce stable repository:

   sudo add-apt-repository ppa:tuxonice/ppa
   

5. Install TuxOnIce kernel & uswsup:

   sudo apt update
   sudo apt install uswsusp linux-generic-tuxonice tuxonice-userui
   

6. Restart your computer (sudo reboot;)

I had the exact same problem in Ubuntu 16.04, and nothing seemed to help.

I finally figured out that I just had to disable Secure Boot in the BIOS menu. I had already done the steps suggested in the accepted answer, so I can't say whether they were necessary in my case.