Dica: ao iniciar o desenvolvimento com Python em uma máquina nova, procure pelo arquivo sitecustomize.py e acrescente:
import sys
sys.setdefaultencoding('utf-8')
O arquivo sitecustomize.py é automaticamente executado toda vez que você executa o Python (sim, você pode fazer o que quiser nele…) Ele fica em lugares diferentes dependendo da plataforma e da sua instalação do Python. No Ubuntu, fica em /usr/lib/python2.7/ (trocando 2.7 pela versão que você estiver usando.) As linhas acima configuram o encoding padrão como Unicode UTF-8. Claro, você pode configurar outro encoding como o padrão, se preferir.
Recomendo muito que, se você não entende nada de charsets ou nem sabe do que estou falando, use UTF-8.