The PHP interactive shell requires that GNU readline or libedit is compiled statically into the PHP binary. Many distributions only provide shared libraries containing only the readline extension.
If you compile PHP yourself do
./configure --with-readline
or
./configure --with-libedit
(note that you, probably, may not redistribute PHP binaries linked to readline due to incompatibilities between GPl and the PHP license, you'd have to use libedit then, but I doubt you want to redistribute PHP itself anyways. Usage is certainly ok. This doesn't matter for your PHP-base applications. But this is one of the reasons why this doesn't work for most distros ...)
Edit: I just filed a PHP bug to enable readline mode with a shared build, too, maybe i find time to implement it: http://bugs.php.net/bug.php?id=53878