Adding an icon next the premium content title

I was able to add an icon using template_preprocess_node:
see http://api.drupal.org/api/drupal/includes%21theme.inc/function/template_...

Code:

<?php
  $node = $variables['node'];
  $premium = db_result(db_query("SELECT nid FROM {premium} WHERE nid = %d AND end_ts > UNIX_TIMESTAMP()", $node->nid));
  if (!empty($premium)) {
    $variables['premium_icon'] = '<img src="/[PATH]/premium_icon.png" border="0"> ';
  }
  else {
    $variables['premium_icon'] = '';
  }
?>

this gives you a new variable $premium_icon and it's available in node.tpl.php so you can display it anywhere in node template.

Probably $node object contains indicator that show whether it's premium content or not.
try do print_r($node) and see if there is something like $node->premium