There is now finally an official upgrade mechanism for Homebrew Cask (see Issue 3396 for the implementation)! To use it, simply run this command:

brew upgrade --cask

However this will not update casks that do not have versioning information (version :latest) or applications that have a built-in upgrade mechanism (auto_updates true). To reinstall these casks (and consequently upgrade them if upgrades are available), run the upgrade command with the --greedy flag like this:

brew upgrade --cask --greedy

To get outdated:

brew outdated --cask --greedy --verbose

Use the command brew upgrade in the terminal to update all of the packages. As for rebuilding all of your programs for the new OS build, there is no reason to do this as the compiled binary should result as the same. If you are noticing any issues, I would just uninstall and reinstall the packages that you are having issues with.

If you're only trying to upgrade one package:

brew upgrade package_name

All packages

brew update && brew outdated && brew upgrade && brew cleanup

Note, I had to add my own answer for this since I got here looking for just one, and noticed the top answer had brew upgrade --cask, while I got the following from here:

During 2020 the sub-commands of the cask command were gradually integrated into the core of Homebrew and were deprecated. The core commands now operate on both formulae and casks. To limit their scope to only formulae or casks add the --formula or --cask option to the command line.

The cask command has been completely removed from Homebrew in version 2.6.0, released in December 2020.

There is a unified flow now for both formulae and casks:

brew update
brew outdated
brew upgrade

The first command (brew update) gets from the Homebrew servers the information about the most recent versions of the available formulae and casks.

The second command (brew outdated) lists the outdated installed formulae and casks. Add --formulae or --casks to the command line to limit the command scope to formulae or casks. Add --greedy to the command line to include in its output the casks that are marked as "auto-updateable". This command is not needed. It can be used to see what programs will be upgraded before doing the actual upgrade.

The third command (brew upgrade) upgrades the packages listed by brew outdated. It also supports the options listed above for brew outdated and operates accordingly.

2023 update

Running brew update is not needed any more since Homebrew version 3.0 or so. When it needs fresh information about packages, Homebrew runs brew update --auto-update and caches the information for about 10 minutes.

The commands to run now are:

brew outdated
brew upgrade
brew cleanup

Read below about the meaning and usage of brew outdated and brew upgrade.

brew outdated is not really needed but it helps you to have an overview of what needs to be upgraded, before doing the actual upgrade. You can decide to not update all formulae and casks blindly (by running brew upgrade without arguments) but to upgrade only some packages (by adding the package name(s) in the command line).

You may also decide to pin some formulae to their current versions using brew pin <formula>; brew upgrade ignores the pinned formulae.
A command to pin the casks is not provided because it is not possible to pin a cask to a certain version. As Homebrew FAQ explains, when a software program uses built-in mechanisms to upgrade itself, pinning the cask to a certain version can lead to inconsistency between the version reported by Homebrew (the one that it tries to pin the cask to) and the actual version of the software, updated by its built-in mechanism. For such software programs, the pin does not actually work, but only produces confusion.

The last command (brew cleanup) removes the old versions of the installed packages from its local cache. Homebrew keeps in a cache the package used to install the current version of a formula or cask.
This command is also not really needed any more, Homebrew cleans the old source packages after it upgrades a formula or a cask. However, brew cleanup is still helpful because it removes (many and small) other files that are not needed any more (logs, caches, etc.)

2021 update

During 2020 the sub-commands of the cask command were gradually integrated into the core of Homebrew and were deprecated. The core commands now operate on both formulae and casks. To limit their scope to only formulae or casks add the --formula or --cask option to the command line.

The cask command has been completely removed from Homebrew in version 2.6.0, released in December 2020.

There is a unified flow now for both formulae and casks:

brew update
brew outdated
brew upgrade

The first command (brew update) gets from the Homebrew servers the information about the most recent versions of the available formulae and casks.

The second command (brew outdated) lists the outdated installed formulae and casks. Add --formulae or --casks to the command line to limit the command scope to formulae or casks. Add --greedy to the command line to include in its output the casks that are marked as "auto-updateable".
This command is not needed. It can be used to see what programs will be upgraded before doing the actual upgrade.

The third command (brew upgrade) upgrades the packages listed by brew outdated. It also supports the options listed above for brew outdated and operates accordingly.

The original answer and the 2018 update are kept for historical reasons.

2018 update

In the meantime, the command brew cask upgrade has been implemented and can be used instead of brew cask reinstall in the script provided in the original answer.

It also works without arguments and upgrades all the casks displayed by brew cask outdated. It can replace the for block in the script that now becomes:

# Upgrade Homebrew and the information about formulas
$ brew update
# List the outdated casks (optional)
$ brew cask outdated
# Upgrade all outdated casks
$ brew cask upgrade

Additional info

Sometimes, brew cask outdated does not list all the outdated casks. This is by design. Some casks mark themselves as auto-updateable while others use the keyword latest as their version. These two categories of casks are not listed by brew cask outdated. To list them one have to add the --greedy option in the command line of brew cask outdated:

$ brew cask outdated --greedy

This command includes in its output the casks mentioned above. Those having latest as their version cannot be checked and are always listed, those marked as auto-updateable are checked and listed only if they are outdated indeed.

The command brew cask upgrade also accepts the --greedy option (internally it uses brew cask outdated to find the list of packages to upgrade). Using it ensures your system is up to date with the additional cost of reinstalling some applications that are not outdated.

The original answer (July 2017)

You are mixing brew commands with brew cask commands and it doesn't work this way.

Homebrew Cask is a component of Homebrew that allows management of graphical applications. It started as an extension of the original Homebrew; it is now an integrated command of brew. Homebrew itself manages only command line applications.

Upgrading command line programs

Upgrading all outdated programs installed with brew (command line programs) is easy:

# Tell Homebrew to update itself and its taps (repositories of programs)
$ brew update
# List the outdated programs
$ brew outdated
# Upgrade all the outdated programs and their dependencies
$ brew upgrade

The brew update and brew outdated steps are optional. brew upgrade internally calls brew update if the last update happened too much time in the past. brew outdated only lists the outdated installed programs; it is useful if you do the upgrade manually and you don't want to upgrade everything. In this case you can pick the programs you want to upgrade and run brew upgrade <program> for each program you want to update. Replace <program> with the package name displayed by brew outdated.

Upgrading graphical programs

Upgrading all outdated graphical programs is not that straightforward at the moment. The process is slightly different than the above.

The first step is to run brew update. It updates Homebrew code and the taps (a tap is a repository of programs managed by Homebrew). Homebrew Cask provides the sub-command brew cask update but it is just an alias of brew update. You can use any of them; brew update is preferred because it is shorter.

The second step is to run brew cask outdated. This command shows the list of outdated programs managed by Cask, together with the installed version and the new version. The option --quiet tells it to show only the package names, without versions. You'll need this for automation on the third step.

The next paragraphs are deprecated since 2018, when the command brew cask upgrade has been implemented. The new flow is described in the section "2018 update" above.

Unfortunately there is no brew cask upgrade command at this moment (it is planned but not implemented yet). brew upgrade doesn't know how to handle the programs installed by brew cask either.

brew cask reinstall can be used instead of the missing brew cask upgrade. Unlike brew upgrade, that upgrades all the outdated packages, brew cask reinstall requires the name of one and only one package. This requires looping through the list returned by brew cask outdated.

A short shell script that upgrades all outdated programs installed using Homebrew Cask can look like this:

brew update
for i in $(brew cask outdated --quiet); do
    brew cask reinstall $i
done

Drawbacks

There are programs that require administrator rights to install drivers or other system components. Some of them ask for your password or for various confirmations using a graphical dialog box. brew cask itself sometimes asks for your password in the command line.

All these make upgrading the outdated programs automatically not always possible.

You may think that all these can be circumvented using sudo. However, the Homebrew developers know better and they programed the brew command to display a message and exit when it is executed as root (and this is the right way to do it.)