How did you install Homebrew? Their official installation instructions include running a ruby script. That should take care of the permission issues for you.
If you don't want to run a script, there is a section of that page called "Installing to /usr/local for Developers" that explains the change in permissions needed for the /usr/local directory.
You'll have to give yourself ownership of /usr/local/ using that line right there. I had to do this myself after using the ruby one-liner at the top of the official docs to install Homebrew. Worked like a charm for me. It ought to be the only time you'll ever need to sudo with Homebrew.
I'm not sure if the ruby one-liner does this. If it did, then something else on my system took control of /usr/local since.
Edit: I completely missed this, but @samvermette didn't (see replies to my answer): if you run this command above and have something installed via homebrew that requires special user permissions, like mysql, make sure to give those permissions back (as the above command gives recursive ownership to everything inside /usr/local to you ($USER). In the case of mysql, it's…
I had this issue after upgrading to Mavericks, and this page was the top search result when googling the error message. I continued searching and found this answer on stack overflow.com. Put concisely, it is:
sudo chmod a+w /usr/local/Cellar
This fixed the issue for me, and as it only changes permissions for the specific path referenced in the error message, seemed unlikely to have negative side effects with other installations.
I'm putting this answer here for anyone else who may find this page first like I did. However, credit should go to jdi.
I suggest ensuring that the current user is a member of the group that owns /usr/local. I believe by default, that group is wheel. To make yourself a member of that group:
Although something of an inelegant hammer, it has the intended effect - enabling access to items in /usr/local that are intended only for use (read/write) by elevated members. This approach has benefits of the other above because it takes advantage of the group memberships, enabling multiple (authorized) users on the system to use homebrew.