How do I change the output of theme_comment_submitted()?
Add a function in your template.php located in your theme's directory.

function phptemplate_comment_submitted($comment){
  return t('Submitted on @datetime by !username.',
    array(
      '!username' =&gt; theme('username', $comment),
      '@datetime' =&gt; format_date($comment-&gt;timestamp)
    ));
}