sudo aptitude install php5-dev libedit-dev

Now, get the source of php5:
apt-get source php5-cli

cd to the readline extension, then compile it:
cd php5-5.3.3/ext/readline phpize ./configure make

copy the compiled extension somewhere (I use /usr/local/lib/php5):
sudo cp modules/readline.so /usr/local/lib/php5/

now, we must tell php to load this extension:
echo extension=/usr/local/lib/php5/readline.so > /etc/php5/conf.d/readline.ini

That's all. Now, everytime you invoke php, the readline extension will be available.

to be sure, execute:
php -m | grep readline

If you use apache2, you have to restart it:
sudo /etc/init.d/apache2 restart