I can confirm that it works with Ubuntu 16.04LTS. If you use the unifying receiver that came with the mouse it will already be paired when you plug it in. If you wish to pair to a pre-existing unifying receiver you should install Solaar, which provides basic control over pairing, and limited configuration options for some Logitech peripherals.
I used a pre-existing unifying receiver, and paired my MX Master to it using Solaar. It does detect battery strength, but does not provide configuration of gestures, dpi, scrolling, etc. The mouse's standard configuration seems to be fine, except that it would really be nice if I could configure the hidden thumb button to switch workspaces for me. The hidden thumb button creates a key sequence, so I guess I could map that sequence within Linux to do workspace swaps.
Anyway, aside from minimal support for configurability, it works great.
I have also paired it using Bluetooth. Doing so required installing blueman and trusting the device.
As an update: The MX Master continues to work under Ubuntu 17.04 just as it did under Ubuntu 16.xx versions.