Developers often attack this problem from "how can I do everything (DomainKeys, et al) to ensure the message will not end up in someone's spam box?".
I used to work on a website that mailed 20,000 users weekly.
The key point in keeping out of the spam box - beyond all the technical components laid out in the link above posted by Martin - is making sure that your recipients do not spam-can you.
Bayesian detection algorithms on mail servers source data from users who click "this is spam" in their mail clients, so if your users think you are SPAM, you are - and you'll get lower delivery percentages (be prepared: 100% is impossible).
Use your brand or website name as the From:
field. Your customer is most likely to remember that, if nothing else. Attempts to "be close" to the customer by using a name of someone in your organization is usually a bad idea, even if you're consistent. Identify your organization UP FRONT, and in the subject line every time.
Make the unsubscribe link incredibly easy to find (not at the bottom!). Users will say "this is spam" to make the message go away if they can't figure out how to get off your list. You don't want these people on your list anyhow.
Double opt-in. Don't add anyone to your list without their explicit opt-in. Not only do you have their blessing, but the delivery of the opt-in message indicates that they're getting your mail. The ever-famous "call to action" of "please add us to your address book" is viable, but I personally never do this when a service asks me to.
Have a schedule on which you send, to whatever the user has agreed (weekly, monthly, etc). If you are not consistent, users will forget registering with you and the mail will seem random. Also, allow them to change the frequency as the next link right next to "unsubscribe" - many people unsubscribe because they are annoyed by too-frequent messages.