An "open relay" is a server that allows third-parties (non-customers) to send mail to other third-parties. In other words, an open relay mail server processes a mail message where neither the sender nor the recipient is a local user.  

There are several techniques that spammers use to get other's mail servers to send their mail. (The spammer's goal is to be able to send to the outside -- not just to the local accounts.) The following are some of the techniques used to try to get a mail server to relay mail. (Some other techniques include abusing form-to-mail CGIs on webservers.)

Originally posted by Err0r
You could just go to http://www.abuse.net/relay.html and test your server for all the checks automagically.