To find and delete the malware, check the running process list in Activity Monitor (or
ps aux from the command line). In my case, there were several process running under root named "GlobalSearch", and variants thereof.
By taking the process id (also known as pid. e.g. value 305) and executing
lsof -p 305 I could see which files on the file system were being accessed.
This pointed me to a python script which was located in
/var/root/.GlobalSearch - a hidden folder under the root user.
sudo rm -rf /var/root/.GlobalSearch deletes the hidden folder and all of it's contents.
At this point, the processes disappeared from Activity Monitor, however Safari (and other system apps) were unable to access the internet.
I then found that this malware had setup a socks proxy in order to send all web traffic to the python script. Open
System Preferences -> Network -> Advanced -> Proxies and uncheck the Socks Proxy checkbox.
I believe the attack vector was a fake Adobe Flash updater which tricked the user into typing in their admin password after downloading the installer.
EDIT: I also ran EtreCheck which found several files that I missed. If you have having this problem, get and run EtreCheck.
I removed the following: