Does Spotlight normally index links in ~/Applications? I have installed MacVim through homebrew, and this resulted in an alias in ~/Applications that points to /usr/local/Cellar/macvim/7.3-66/MacVim.app.

Unfortunately MacVim does not show up in Spotlight searches. Is this normal?
It's actually a symlink and not an alias. Spotlight indexes symlinks to files that are treated as system files, but it doesn't show them in the GUI. It does show aliases though, so you could just command-option-drag /usr/local/Cellar/macvim/*/MacVim.app to /Applications from Finder.

Or convert the symlinks to aliases:

brew linkapps; find ~/Applications -type l | while read f; do osascript -e "tell app \"Finder\" to make new alias file at POSIX file \"/Applications\" to POSIX file \"$(/usr/bin/stat -f%Y "$f")\""; rm "$f"; done


Or if you use Alfred, it can be set to include applications in /usr/local/Cellar in the default search results.