What is the most semantic way to display a street address in HTML?

You could use the hCard Microformat to describe your address. The advantage of Microformats is that you can use them in your existing documents to enrich them.

Here’s an example derived from the example from the Microformats wiki:

<address class="vcard">
  <span class="adr">
    <span class="street-address">169 University Avenue</span>
    <span class="locality">Palo Alto</span>,  
    <abbr class="region" title="California">CA</abbr>&nbsp;&nbsp;
    <span class="postal-code">94301</span>
    <span class="country-name">USA</span>
  </span>
</address>

The answer by Gumbo is missing an ingredient. An hcard/vcard is required to have a name (fn).

http://microformats.org/wiki/hcard#Property_List

Also the address tag should not be used in this case as it is specifically used to relate to the author of the page it is displayed on.

<div class="vcard">
  <span class="fn">Tristan Ginger</span>
  <span class="adr">
    <span class="street-address">169 University Avenue</span>
    <span class="locality">Palo Alto</span>,  
    <abbr class="region" title="California">CA</abbr>
    <span class="postal-code">94301</span>
    <span class="country-name">USA</span>
  </span>
</div>

Most business wanting to display their address on their website should use the following:

<address class="vcard">
  <span class="fn org">Tristan Ginger Inc</span>
  <span class="adr">
    <span class="street-address">69 University Avenue</span>
    <span class="locality">Great Bookham</span>,  
    <span class="region">Surrey</span>
    <span class="postal-code">KT22 9TQ</span>
    <span class="country-name">UK</span>
  </span>
</address>

you can use RDFa, eg:

<html
    xmlns="http://www.w3.org/1999/xhtml"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:address="http://schemas.talis.com/2005/address/schema#"
    xml:lang="fr" lang="fr"
>
 <head>...</head>
 <body>
  <div typeof="foaf:Person" about="http://you.openid.com#me">
   <span id="name" property="foaf:name">First Name, Last Name</span>
   <address property="address:streetAddress">My Street, My City</address>
  </div>
 </body>
</html>