Use the translation file translate.csv in your theme.
For demonstration purposes, I will use the default theme in the default package (app/design/frontend/default/default). You may apply the steps below to your custom theme.
How to change the label using the translation file:
- Open app/design/frontend/default/default/locale/en_US/translate.csv
Add a new line:
"Billing Information","Shipping and Billing Information"
Verify that your Store View uses the correct locale ("en_US").
Log in to the Magento backend and navigate to System > Configuration > General > General > Tab "Locale Options". The "Locale" has to be set to "English (United States)" (either by directly setting it for the particular Store View or by inheriting from the Website / Default configuration).
Verify that your Store View uses the default/default directory. This can be set in System > Configuration > General > Design. By default, "default/default" is used.
Refresh or deactivate the cache.
Navigate to the checkout page. The label text now should be "Shipping and Billing Information".
How to change the text only for Mage_Checkout texts:
If you want to change "Billing Information" only in these places where the checkout translation helper is used, you can modify the line in translate.csv like this:
"Mage_Checkout::Billing Information","Shipping and Billing Information"