IMHO, the easiest way to do this is to install postfix (if debconf asks you questions, pick "internet site"), then run these commands:
postconf -e relayhost=other.mailserver.com
postconf -e mailname=my.domainname.com
As long as the SMTP server specified in relayhost doesn't require authentication, allows you to relay or is a valid destination for the recipient address this will work.
The mailname parameter will be the default domain name. So if you send mail to foo it will go to foo@my.domainname.com. Mail sent by user bar will be from bar@my.domainname.com.
If you do need to authenticate and want to support TLS, also run the following commands:
postconf -e smtp_tls_security_level=may
postconf -e smtp_sasl_auth_enable=yes
postconf -e smtp_sasl_password_maps=pcre:/etc/postfix/sasl_password_maps
Then in /etc/postfix/sasl_password_maps have this content:
/./ username:password
All mail will be sent to your relayhost with the specified username and password.
postfix'cause it's awesome? – xenoterracide♦ Sep 1 '10 at 0:58