phpsh requires readline support built into python. It also requires python version 2.4+. You can check which version of python you have installed by typing:
python -V
Let us download and install readline:
wget ftp://ftp.cwru.edu/pub/bash/readline-5.2.tar.gz
tar zxf readline-5.2.tar.gz
cd readline-5.2
./configure
make install
Now let us install python with readline support:

wget http://www.python.org/ftp/python/2.5.1/Python-2.5.1.tgz
tar zxf Python-2.5.1.tgz
cd Python-2.5.1

I had some problems on one of the [...]