In older versions of the NetworkManager gui there was a field for the search domain to be written into /etc/resolv.conf, but it was dropped by the time Ubuntu 18.04 LTS shipped. You can add it by editing the system-connections file directly, but running the appropriate nmcli commands is the right way to do it. Note that Ubuntu Server 18.04, which use netplan and systemd-networkd by default, is completely different. Ubuntu 20.04 involves even more variation (see comments below). It's enough to drive someone to Debian proper...
First, get the name of the interface you want to set a search domain on:
$ nmcli con show