On debian jessie, install the ubuntu packages with the following commands:
Add deb http://ppa.launchpad.net/neovim-ppa/unstable/ubuntu vivid main to /etc/apt/sources.list (debian jessie and ubuntu vivid are both released in april 2015). Then run:
sudo apt-key adv --recv-keys --keyserver keyserver.ubuntu.com 55F96FCF8231B6DD
sudo apt-get update
sudo apt-get install neovim
Continue as described in https://github.com/neovim/neovim/wiki/Installing-Neovim#ubuntu:
sudo update-alternatives --install /usr/bin/vi vi /usr/bin/nvim 60
sudo update-alternatives --config vi
sudo update-alternatives --install /usr/bin/vim vim /usr/bin/nvim 60
sudo update-alternatives --config vim
sudo update-alternatives --install /usr/bin/editor editor /usr/bin/nvim 60
sudo update-alternatives --config editor