Looking up helped.
Just need to have a file called .pythonrc in your home directory containing the following:
print "Module readline not available."
Apparently, that was not enough. I also needed to add the following line to my .bashrc file (in my home directory again).
That's all. Open a new shell and start the python shell.
And enjoy auto-completion!