For posterity (I actually needed to install this today):

You need to install zsh-autosuggestions by installing the package from your distribution (Debian, Arch) and source it, or just run:

    git clone https://github.com/zsh-users/zsh-autosuggestions ${ZSH_CUSTOM:-~/.oh-my-zsh/custom}/plugins/zsh-autosuggestions

in zsh and do exec zsh.