An anonymous remailer is a computer which has been configured to run remailer software. This software is a specialized kind of email server software. Unlike the average email server which goes to great lengths to log all incoming/outgoing traffic and add identifying and traceable info to its outgoing mail (in the form of headers) remailer software ensures that outgoing mail has been stripped clean of any identifying information! Thus the name 'anonymous' remailer.
There are two types of remailer - Type 1 and Type 2. Type 1 remailers are known as Cypherpunk remailers. Messages are written in a special format in any normal text editor, and then encrypted with Public Key Cryptography, such as PGP by Phil Zimmerman. This is then placed placed in a normal email to the remailer's address with a directive above telling the remailer that it is encrypted with PGP.
The remailer decrypts the message and sends the anonymous email to the person specified within. However, thats only the beginning of remailer capabilites. The fun really starts when you chain messages.
Chaining is a procedure whereby you choose a chain of remailers that you have the public keys for, and then encrypt the final plaintext email to the public key of the last remailer in the list. You then encrypt that message with the key of the second last remailer and so on, and each remailer will decrypt one layer of encryption, and send the next layer on to the next remailer who will decrypt that and so on. When it gets to the last remailer in the chain, it will send it off the human recipient. The advantage of chaining is that if one remailer is compromised, it wwill not affect the security of your message.
Type 2 remailers are known as Mixmaster remailers. These are intended by the designer of the Mixmaster software to simplify the proces of chaining messages, and keeping track of keys. Mixmaster messages cannot be created in the same way as Cypherpunk messages, and require a Mixmaster client, a command line program to manage keys and create messages. People have also written GUIs for Mixmaster, such as JBN and Quicksilver which make it easier for less savvy users to make use of these features.
Anonymous remailers are a good way to send anonymous messages to M2N gateways.