Postini acts as a filtering SMTP relay. You set your MX records to Postini's servers, and tell Postini what the original MX records were.
Servers delivering mail to your domain check the MX records, and deliver the message to Postini. Postini rejects the spam and then itself sends the non-spam to the original servers using the same SMTP process as when it received the message (except for the EHLO).
Ideally, you configure the original servers to only accept mail from Postini, so that spammers can't bypass Postini by sending directly to those servers (e.g. if the mail server and A record are the same, the spammer is likely to try the A record as well).