Eu vou assumir que você tem o Debian lenny e ter seu sourcelist voltado para o lançamento estável que por padrão tem apenas python2.5 (alguém me corrige?)
A partir de uma breve varredura de sua árvore de pacotes, o python3.1 existe na árvore Debian Sid (instável) e Debian Squeeze (testing). Veja aqui
Você pode w-get
diretamente dos links fornecidos, mas isso é sempre confuso, pois você mesmo precisará resolver quaisquer dependências através de um jogo o que eu não tenho? com o CLI.
Se você está apto a mudar a sua árvore de pacotes para o squeeze, você pode mudar o seu /etc/apt/sources.list
para coincidir com o da squeeze tree. De lá, você pode aptitude update
then aptitude install python
e você deve ter python3.1 e todas as suas dependências a reboque.