You create your API token on https://github.com/settings/tokens
and then set the environment variable HOMEBREW_GITHUB_API_TOKEN to the value of your token.
When creating the token, make sure that you only select the scopes you need. As pointed out in the answer by Chad, leaving all of the scopes unchecked is very reasonable!
Setting the token is done using the export command. Example:
export HOMEBREW_GITHUB_API_TOKEN=xxxx
To make sure this is set whenever you open a terminal you can add this command to your ~/.brew_bashrc or ~/.bash_profile or any other file that is used during the initialisation of your shell file.
For future reference, this topic was discussed in the following two issues:
- https://github.com/mxcl/homebrew/issues/21023
- https://github.com/mxcl/homebrew/issues/21915