Díky, kluci!
Nakonec se použil následující kód:
$query = ('SELECT DISTINCT state,city FROM table ORDER BY state ASC, city ASC');
$result = mysql_query($query);
$states = array();
while ($row = mysql_fetch_assoc($result)) {
if (!isset($exists[$row['state']])) {
echo "<div id='location'><div class='state'><p>" . $row['state'] . "</p>";
$exists[$row['state']] = true;
}
echo "<div class='city'><p><a href='?city=".$row['city']."' target='_blank'>".$row['city']."</a></p></div>";
}