There are some problems with readline support in Python on Mac OS X. It is because Apple doesn't supply a readline on the system (or a broken one, I dont remember). In any case, you need to download and install a correct readline yourself.
In my case, I use the one that comes as part of Fink. (Alternatives exist, such as darwinports or getting and building just the readline code itself). To make the Python 2.5 setup tool recognise fink's readline, I had to run the configure script like this:
~$ LDFLAGS=-L/sw/lib CPPFLAGS=-I/sw/include ./configure
otherwise the fink include- and libfiles won't be found. Note that for Python 2.4 this is not needed, the setup.py from that version knows about Fink and will find the readline lib by itself...
(more info in this message on python-dev. Also see →Command-line tab completion in standard Python shell about command-line tab completion and readline)