How should I store global information such as a phone number so that it is editable through the CMS?

Right now I have a p element in header.php containing the address and phone number my client wishes to use for contact info. How can I set this up so that it is editable through the WP admin area so that my client can easily change this in the future?

Store it in your theme options. Read the series of articles called The Complete Guide To The WordPress Settings API. Spare no effort to read it, especially 4th article about Theme Options.