PS there may be other steps involved on the other host in order to get it to actually send email to a remote server instead of delivering it locally, but as for the DNS part of things, that is what the other host needs to know. Then tell them that you plan on hosting the mail off site and they should be able to make the adjustments for you.