You'll need to modify two files:

First: includes/languages/english/checkout_payment.php

create a new define statement

Code:
define ('TEXT_CUSTOMER_MESSAGE', 'To place your order using payment other than Paypal, please contact us at 503-231-1121 or email [email protected]. Thank you.');
Save the file to includes/languages/english/YOUR_TEMPLATE/checkout_payment.php and upload to you server

two: includes/templates/template_default/templates/tpl_checkout_payment_default.php

find:
Code:
<h1 id="checkoutPaymentHeading"><?php echo HEADING_TITLE; ?></h1>
below this line add the following:
Code:
<?php echo TEXT_CUSTOMER_MESSAGE; ?>
Save the file to includes/templates/YOUR_TEMPLATE/templates/tpl_checkout_payment_default.php and upload to your server