Você deve conseguir instalá-lo através do Eclipse. A página do PyDev tem as instruções sobre como fazer isso .
Se você não estiver usando o Aptana, role para baixo até Instalando com o site de atualização e comece por lá. Você começará analisando Ajuda > Instalar novo software ...
Eu apenas fiz isso em 12.04 e até agora tudo parece estar funcionando bem.