sudo apt-get install libreadline-dev
должен это сделать.
Похоже, вы также захотите
sudo apt-get install libncurses5-dev