Computer programs use something called an encoding to turn human-language characters into bytes that the computers can swap back and forth, and to turn those bytes back into characters. If one program (your contact's client) sends text in one encoding, but the other program (your client—that is, Adium) is expecting a different encoding, then the receiving program may show the wrong characters.

By default, Adium always uses UTF-8 encoding given that both sides support it. You can tell Adium which encoding to expect if your contact a) doesn't support UTF-8 and b) doesn't specify its encoding to Adium. The setting for this is to be found in the Options tab of your ICQ account in Adium.

Changing the encoding doesn't affect messages you've already received; the change only applies to messages you receive after you click OK.