Okay, I finally got around to doing this and once I really started looking it wasn't all that hard...
In lang/english.php (or in the language of your choice), find these lines:
$lang_thumb_view = array(
'date' => 'DATE',
//Sort by filename and title
'name' => 'FILE NAME',
'title' => 'TITLE',
'sort_da' => 'Sort by date ascending',
'sort_dd' => 'Sort by date descending',
'sort_na' => 'Sort by name ascending',
'sort_nd' => 'Sort by name descending',
'sort_ta' => 'Sort by title ascending',
'sort_td' => 'Sort by title descending',
'position' => 'POSITION', //cpg1.4
'sort_pa' => 'Sort by position ascending', //cpg1.4
'sort_pd' => 'Sort by position descending', //cpg1.4
After these, add the following:
'rating' => 'RATING',
'sort_ra' => 'Sort by rating ascending',
'sort_rd' => 'Sort by rating descending',
In include/functions.inc.php, find the following section:
$sort_array = array(
'na' => 'filename ASC',
'nd' => 'filename DESC',
'ta'=>'title ASC',
'td'=>'title DESC',
'da' => 'pid ASC',
'dd' => 'pid DESC',
'pa' => 'position ASC',
'pd' => 'position DESC',
After this, add the following:
'ra' => 'pic_rating ASC, votes ASC',
'rd' => 'pic_rating DESC, votes DESC',
Now in include/themes.inc.php, find the following:
$param = array('{ALBUM_NAME}' => $album_name,
'{AID}' => $aid,
'{PAGE}' => $page,
'{NAME}' => $lang_thumb_view['name'],
'{TITLE}' => $lang_thumb_view['title'],
'{DATE}' => $lang_thumb_view['date'],
'{SORT_TA}' => $lang_thumb_view['sort_ta'],
'{SORT_TD}' => $lang_thumb_view['sort_td'],
'{SORT_NA}' => $lang_thumb_view['sort_na'],
'{SORT_ND}' => $lang_thumb_view['sort_nd'],
'{SORT_DA}' => $lang_thumb_view['sort_da'],
'{SORT_DD}' => $lang_thumb_view['sort_dd'],
'{POSITION}' => $lang_thumb_view['position'],
'{SORT_PA}' => $lang_thumb_view['sort_pa'],
'{SORT_PD}' => $lang_thumb_view['sort_pd'],
After it, add this:
'{RATING}' => $lang_thumb_view['rating'],
'{SORT_RA}' => $lang_thumb_view['sort_ra'],
'{SORT_RD}' => $lang_thumb_view['sort_rd'],
While still in include/themes.inc.php, find this section:
<tr>
<td class="sortorder_options">{POSITION}</td>
<td class="sortorder_options"><span class="statlink"><a href="thumbnails.php?album={AID}&page={PAGE}&sort=pa" title="{SORT_PA}"> + </a></span></td>
<td class="sortorder_options"><span class="statlink"><a href="thumbnails.php?album={AID}&page={PAGE}&sort=pd" title="{SORT_PD}"> - </a></span></td>
</tr>
Add this after it:
<tr>
<td class="sortorder_options">{RATING}</td>
<td class="sortorder_options"><span class="statlink"><a href="thumbnails.php?album={AID}&page={PAGE}&sort=ra" title="{SORT_RA}"> + </a></span></td>
<td class="sortorder_options"><span class="statlink"><a href="thumbnails.php?album={AID}&page={PAGE}&sort=rd" title="{SORT_RD}"> - </a></span></td>
</tr>
Note that if your theme has a custom value for $template_thumb_view_title_row in its theme.php, you will have to modify your theme to display the rating sort option similar to that last HTML block.