If you use homebrew, you can do the following (assume you are installing evernote):
% brew tap phinze/cask
% brew install brew-cask
% hash -r
% brew cask alfred link
% brew cask install evernote
Now, typing "Ev…" should autocomplete to "Evernote". Apps are installed to "/opt/homebrew-cask/Caskroom" and this directory is indexed by alfred after typing "brew cask alfred link".