If you've been using Homebrew for a while, you may have built up some cruft in the form old and outdated files. These will not be cleaned up automatically. You have do tell Homebrew to do so. This can be done with the following command.
$ brew cleanupThis command will report what files it cleans up as well as how much disk space it was able to clear.
See man brew for more details.
h/t Dorian Karter