The Step by step introduction to switching your debian installation to utf-8 encoding is a good guide. It's worth pulling a bit of it out for a common use-case: you use GNOME and gdm, and pretty much everything takes place inside that. This is what you'd do:

1. As root, run

   dpkg-reconfigure locales

2. Generate an appropriate locale for yourself, and select the UTF8 version (it has UTF8 on the end). I use Australian English, which is en_AU.UTF8. If you have users of more than one language, generate the UTF8 versions of their languages too, if available.

3. If you're your machine's only or main user, or all your users will want the same locale, set the default to your locale of choice and you're all set, save that you will need to log out and log back in. You're done.

4. If you have multiple users with different languages, don't set a default locale. Provided you are a using GNOME logins via gdm, setting a user-specific locale for yourself is not difficult:

   1. Log out

   2. If you know how to get a root shell, get one and run

      /etc/init.d/gdm restart
      Otherwise, just reboot.

   3. When the gdm login screen comes back up, click on the Languages button before you log in and select your UTF8 locale.

   You may see this error (or a version for your own locale) appear in a dialog box:

   Language en_AU does not exist, using System default.

   This can be quite puzzling when you have just selected the locale from a dialog box, but it occurs when you didn't restart gdm itself before trying to log in with your new locale. You can't just log out, you must restart gdm.