If you want to change the default address representation in your Magento shop you should simply add new address format for desired country. It should be done in the table mage_directory_country_format.

The following example illustrates how to do this. This statemet inserts the same format in three forms: HTML, text and PDF for beeing used in PDF documents like invoices.

INSERT INTO `mage_directory_country_format` (`country_id`, `type`, `format`) VALUES
('DE', 'html',
'{{depend company}}{{var company}}<br />{{/depend}}\n
{{var firstname}} {{var lastname}}<br/>\n
{{var street1}}<br />\n
{{depend street2}}{{var street2}}<br />{{/depend}}\n
{{depend postcode}}{{var postcode}}{{/depend}}{{depend city}} {{var city}}{{/depend}}
{{depend region}}, {{var region}}{{/depend}}<br/>\n
{{var country}}<br/>\n{{depend telephone}}Tel : {{var telephone}}{{/depend}}\n
{{depend fax}}<br/>Fax : {{var fax}}{{/depend}}'),
('DE', 'text',
'{{depend company}}{{var company}}\n{{/depend}}
{{var firstname}} {{var lastname}}\n
{{var street1}}{{depend street2}}{{var street2}}\n{{/depend}}\n
{{depend postcode}}{{var postcode}}{{/depend}}{{depend city}} {{var city}}{{/depend}}
{{depend region}}, {{var region}}{{/depend}}\n
{{var country}}
{{depend telephone}}\nTel : {{var telephone}}{{/depend}}
{{depend fax}}\nFax : {{var fax}}{{/depend}}'),
('DE', 'pdf',
'{{depend company}}{{var company}}|\n{{/depend}}
{{var firstname}} {{var lastname}}|\n
{{var street1}}|{{depend street2}}{{var street2}}|\n{{/depend}}\n
{{depend postcode}}{{var postcode}}{{/depend}}{{depend city}} {{var city}}{{/depend}}
{{depend region}}, {{var region}}{{/depend}}|\n
{{var country}}
{{depend telephone}}|\nTel : {{var telephone}}{{/depend}}
{{depend fax}}|\nFax : {{var fax}}{{/depend}}|')

Prioduces something like:
My Company GmbH
Max Mustermann
Mönkeberg Str. 123
22090 Hamburg
Hansestadt Hambug
Deutschland