If they followed the readme, it's in includes/templates/YOUR_TEMPLATE/common/tpl_footer.php
from README for 1.3 x.txt
Code:
SETUP INSTRUCTIONS:
===================
1. In includes/templates/YOUR_TEMPLATE/tpl_footer.php:
replace:
<!--bof- site copyright display -->
<div id="siteinfoLegal" class="legalCopyright"><?php echo FOOTER_TEXT_BODY; ?></div>
<!--eof- site copyright display -->
with:
<!--bof- site copyright display -->
<div id="siteinfoLegal" class="legalCopyright"><?php echo FOOTER_TEXT_BODY; ?>
<?php if ($_GET['main_page'] == 'checkout_shipping' || $_GET['main_page'] == 'checkout') { ?>
<br />
<center>FedEx service marks used by permission.</center>
<?php } ?>
</div>
<!--eof- site copyright display -->