It is not just the character set that has to be changed. What is sent when you press the keys (e.g. åäö) has to be changed also.

I did not manage to set Encoding to something that worked. And I have run out of ideas. This is very annoing since I am reading my emails usning emacs running in a screen and not having working åäö is not acceptable.