Para fazer um programa que imprima um caráter com acento, é preciso usar uma codificação excecional. O Unicode devia ser a regra e não a exceção, mas no Python é assim.
Versão sem acentos, num ficheiro batch em Linux
#!/usr/bin/python
print("Ola Mundo")
print('Mais uma frase\n')
Versão Unicode
#!/usr/bin/python
# -*- coding: utf-8 -*-
print("Olá Mundo")
print('Mais uma frase: a fataça e o sururú\n')