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-drag /usr/local/Cellar/macvim/*/MacVim.app to /Applications from Finder.
Or convert the symlinks to aliases:
Or if you use Alfred, it can be set to include applications in /usr/local/Cellar in the default search results.