Theming html output of privatemsg 6.x-2.x module
Ok, here is some information.


That list shows threads, not single messages. You can't change that, at least not with theming. The only thing you easily can do is enable the privatemsg_limits module and set the number of messages per thread to 1. That basically disables threading and each message will be sent as a new thread. Then they will be shown separetly on the list, but they will also be shown separately on the thread view page. Privatemsg views is currently only compatible with 6.x-1.x and looks rather unmaintained at this point.
You can configure the displayed columns and their order in the Privatemsg settings.
The theming functions are used to customize the content of single columns. For example, to show a different date format, you can override phptemplate_privatemsg_list_field__last_updated():

function phptemplate_privatemsg_list_field__thread_started($thread) {
  $field = array();
  $field['data'] = format_date($thread['thread_started'], 'custom', 'd.m.Y H:i');
  $field['class'] = 'privatemsg-list-date-started';
  return $field;
}


In 7.x, Privatemsg shows a different date format depending on the age of the message, that is done in privatemsg_format_date() if you want to backport that.
To change how the table looks, you should be able to that with just CSS. Privatemsg adds tons of classes to that table, including a seperate class for every column and classes for rows with new messages and soon for unreplied messages too.