If you’ve tried using wp_tag_cloud() as an array, you’ve noticed that all it really does is give you a string, which isn’t useful. The only way I could figure out how to get the tags to where I can format them how I want was to call get_tags() in wp-includes/category.php. You can also pass arguments to it to sort it differently. Take a look at get_terms() in wp-includes/taxonomy.php to get an idea of what you can do.
Here is a hack I put together that will output your tags as a unordered list (UL) with the total number of times the tag is used in parenthesis. You can place this code in sidebar.php
$tag_array = get_tags('orderby=count&order=DESC&number=15');
$tag_total = count($tag_array);
for ($x = 0; $x < $tag_total; $x++)
echo '<a href="' . get_option('home') . '/tag/' . $tag_array[$x]->slug . '/" rel="tag">';
echo ' (' . $tag_array[$x]->count . ') ';