BASICALLY an anonymous remailer strips away the "header" from your message (your real name and e mail address), replaces it with a dummy address, and forwards the e mail to the addressee. In turn the computer notifies you of your new anonymous address (e.g. an315.anon.penet.fi) to which the other person can reply. Or, in the case of a one way remailer, no reply is possible.
There are two main types of remailer: Penet (which lets people exchange messages confidentially) and Cypberpunk, which is one way. Their regular users tend to distinguish between "pseudo anonymous remailers" (where the administrator knows your real e mail address) and truly anonymous ones such as Cypberpunk and Mixmaster - but the bad news with the latter is that they are generally much harder to use.
Besides various private remailer services (which restrict their user base) there are over a dozen public ones which are all free. Free? Well, it would be impossible to charge people who want maximum privacy. They can't very well ask you for your credit card number or ring back to check up on you ...