You can use empty() to check if $item1 and $item2 are empty as the following :
$query = "select stores,item1,item2 from wp_dbt_nonnis_distro_data where state = '$_GET[state]' order by stores asc";
$result = mysql_query($query,$conn);
while ($row = mysql_fetch_array($result)){
$stores = $row['stores'];
$item1= $row['item1'];
$item2= $row['item2'];
if ( !empty( $item1 ) )
$new1 = str_replace(',', '</li><li>', $item1);
else
$new1 = 'Not Available';
if ( !empty( $item2 ) )
$new2 = str_replace(',', '</li><li>', $item2);
else
$new2 = 'Not Available';
echo <<<END
<div class="stores">
<h2>Store Name: $stores</h2>
<h3>Brands Carried:</h3>
<div class="items">
<p>Item1</p>
<ul><li>$new1</li></ul>
</div>
<div class="items">
<p>Item2</p>
<ul><li>$new2</li></ul>
</div>
</div>
END;
}