What's the best way to generate a tag cloud from an array using h1 through h6 for sizing?

You will want to add a logarithmic function to it too. (taken from tagadelic, my Drupal module to create tag clouds http://drupal.org/project/tagadelic):

db_query('SELECT COUNT(*) AS count, id, name FROM ... ORDER BY count DESC');

$steps = 6;
$tags = array();
$min = 1e9;
$max = -1e9;

while ($tag = db_fetch_object($result)) {
    $tag->number_of_posts = $tag->count; #sets the amount of items a certain tag has attached to it
    $tag->count = log($tag->count);
    $min = min($min, $tag->count);
    $max = max($max, $tag->count);
    $tags[$tag->tid] = $tag;
}
// Note: we need to ensure the range is slightly too large to make sure even
// the largest element is rounded down.
$range = max(.01, $max - $min) * 1.0001;

foreach ($tags as $key => $value) {
    $tags[$key]->weight = 1 + floor($steps * ($value->count - $min) / $range);
}

Then in your view or template:

foreach ($tags as $tag) {
    $output .= "<h$tag->weight>$tag->name</h$tag->weight>"
}

Off the top of my head...

$artist = array("the roots","michael jackson","billy idol","more","and more","and_YET_MORE");
$count = array(5,3,9,1,1,3);
$highest = max($count);
for (int $x = 0; $x < count($artist); $x++)
{
    $normalized = $count[$x] / $highest;
    $heading = ceil($normalized * 6); // 6 heading types
    echo "<h".$heading.">".$artist[$x]."</h".$heading.">";
}

Perhaps this is a little academic and off topic but hX tags are probably not the best choice for a tag cloud for reasons of document structure and all that sort of thing.

Maybe spans or an ol with appropriate class attributes (plus some CSS)?

Have used this snippet for a while, credit is prism-perfect.net. Doesn't use H tags though

<div id="tags">
    <div class="title">Popular Searches</div>
    <?php
        // Snippet taken from [prism-perfect.net]

        include "/path/to/public_html/search/settings/database.php";
        include "/path/to/public_html/search/settings/conf.php";

        $query = "SELECT query AS tag, COUNT(*) AS quantity
        FROM sphider_query_log
        WHERE results > 0
        GROUP BY query
        ORDER BY query ASC
        LIMIT 10";

        $result = mysql_query($query) or die(mysql_error());

        while ($row = mysql_fetch_array($result)) {

            $tags[$row['tag']] = $row['quantity'];
        }

        // change these font sizes if you will
        $max_size = 30; // max font size in %
        $min_size = 11; // min font size in %

        // get the largest and smallest array values
        $max_qty = max(array_values($tags));
        $min_qty = min(array_values($tags));

        // find the range of values
        $spread = $max_qty - $min_qty;
        if (0 == $spread) { // we don't want to divide by zero
            $spread = 1;
        }

        // determine the font-size increment
        // this is the increase per tag quantity (times used)
        $step = ($max_size - $min_size)/($spread);

        // loop through our tag array
        foreach ($tags as $key => $value) {

            // calculate CSS font-size
            // find the $value in excess of $min_qty
            // multiply by the font-size increment ($size)
            // and add the $min_size set above
            $size = $min_size + (($value - $min_qty) * $step);
            // uncomment if you want sizes in whole %:
            // $size = ceil($size);

            // you'll need to put the link destination in place of the /search/search.php...
            // (assuming your tag links to some sort of details page)
            echo '<a href="/search/search.php?query='.$key.'&search=1" style="font-size: '.$size.'px"';
            // perhaps adjust this title attribute for the things that are tagged
            echo ' title="'.$value.' things tagged with '.$key.'"';
            echo '>'.$key.'</a> ';
            // notice the space at the end of the link
        }
    ?>
</div>

@Ryan

That's correct but it actually makes the tags with the least number, larger. This code has been tested:

$artist = array("the roots","michael jackson","billy idol","more","and more","and_YET_MORE");
$count = array(5,3,9,1,1,3);
$highest = max($count);
for ($x = 0; $x < count($artist); $x++) {
    $normalized =  ($highest - $count[$x]+1) / $highest;
    $heading = ceil($normalized * 6); // 6 heading types
    echo "<h$heading>{$artist[$x]}</h$heading>";
}