How can I customize the display of messages sent with privatemsg?
I've just implemented the Privatemsg Panels plugin with the D7 Patch through the pm_existing_pages plugin and it's working quite well! Here's how it all goes down for Drupal 7:


Grab the master branch of the privatemsg_panels module and upload to your modules directory
Patch Manager is super handy - install it and run the panels_privatemsg7.patch file to upgrade the module to a 7.x branch (or patch by hand or drush or eclipse etc)
Optional: Install PM Existing Pages and add override the default /messages/ path with a new panel. Of course you could create a new panels page just as easily.
Add content to your panel - Privatemsg should be a menu item now: 
Create a nice little custom link block from the instructions over here - might be useful for your particular view!
Optional: override privatemsg-view.tpl.php for a more custom layout. I haven't quite got this far, will try to remember to update this when I give it a shot.


Edit - Adding info!


Overriding privatemsg-view.tpl.php works great, just remember to clear the cache after you add the file to your theme folder.
Take a look at the Privatemsg Theming Documentation. All of  the functions that start with phptemplate_ can be overridden by your own theme. Example: drop this into your template.php file

function YOURTHEMENAME_privatemsg_list_field__participants($variables) {
    $thread = $variables['thread'];
    $field = array();

    if ($thread['has_tokens']) {
        $message = privatemsg_message_load($thread['thread_id']);
    }
    if (!isset($message)) {
        $message = privatemsg_message_load($thread['thread_id']);
    }

    $participants = _privatemsg_generate_user_array($thread['participants'], -4);

    $field['data'] = theme('user_picture', array('account' =&gt; $message-&gt;author));
    $field['data'] .= '&lt;div class="user-name"&gt;'. _privatemsg_format_participants($participants, 3, TRUE).'&lt;/div&gt;';

    $field['class'] = 'privatemsg-list-participants';

    return $field;
}


This will add a user picture to the recipients field! AWESOME! Just remember that each overridden fuction expects to have 3 things returned: a field, a header theme pattern, and a field theme pattern - the documentation explains it better than I can ;)
The functions at the Privatemsg Theming Documentation starting with theme_ can be overridden using a function YOURTHEMENAME_form_alter() hook. If you add this function to your template.php, drop dsm($form_id); dsm($form); in to get a better idea of exactly what form you're working with.
Looking to change column order around? It's easier than you might think - check out the drag-and-drop column order at /admin/config/messaging/privatemsg


There has been a bit of discussion about how to add custom columns to the output but I'm not there yet.. I'll have to point you at the Privatemsg Issue Queue for that one.

Good luck!