If you've just upgraded to Sierra and previously had Homebrew installed you may find that it no longer works because of the stricter security feature in macOS. In order to get Homebrew back up and running you need to execute the following commands in your terminal (thanks thehitmaniptf):
sudo chown -R $(whoami) /usr/local
xcode-select --install
The first command simply gives your local user account ownership of /usr/local (where brew installs things). The second command updates the Xcode command line tools without which Homebrew cannot compile packages.
Once this is done you can successfully update Homebrew as normal, and diagnose any remaining issues:
brew update
brew doctor
After running this you will receive instructions on how to restore the permissions on /usr/local as after updating Homebrew no longer will use this path.
Update 6th Nov, 2016: When using cask you might get told to update the cask room location:
sudo mv /opt/homebrew-cask/Caskroom /usr/local