Use the $messageStack.
An example from the Authorize.net module:
Code:
    // If the response code is not 1 (approved) then redirect back to the payment page with the appropriate error message
    if ($response_code != '1') {
      $messageStack->add_session('checkout_payment', $response_msg_to_customer . ' - ' . MODULE_PAYMENT_AUTHORIZENET_AIM_TEXT_DECLINED_MESSAGE, 'error');
      zen_redirect(zen_href_link(FILENAME_CHECKOUT_PAYMENT, '', 'SSL', true, false));
    }