In Ubuntu GNOME 16.04, you are correct that the ability to edit or add additional search domains is unavailable, but this is only true for the 'default' network editing system that you see. This 'newer' one was put in place, according to Jeremy Bicha in the
#ubuntu-gnome IRC chat channel on Freenode, because the default editor in Settings should be easier to use for most end-users:
jbicha: sorry it's hidden by default because most people don't need two network GUIs and the one in the Settings app should be easier to use for most people
And of course you can't see search domains in the default editor:
However, the original network editing GUI is still available. Just run
nm-connection-editor. This will launch the same, good-old Network Manager editing window that you expect to see. That has the ability to do search domains. (Thanks to the
#ubuntu-gnome IRC channel on Freenode for this!)
This procedure/answer also works in 18.04 and 20.04 as well (tested myself).