[Old Pedant]

Okay, this is really 90% a PHP question and only 10% MySQL.

And I don't use PHP. So bear with me if I make a couple of PHP typos.

<!-- don't use PHP to write out large blocks of HTML -->
<!-- makes it harder to read, harder to write, and tiny bit slower -->
<table border="1"' cellpadding="10">; 
<tr>
    <th><a href="thispage.php?by=nameLast">Last Name</a></th>
    <th><a href="thispage.php?by=nameFirst">First Name</a></th>
</tr>
<?php
// make you db connection here ...

$orderby = $_GET["by"];
if ( ! isset($orderby) || ( $orderby != "nameLast" && $orderby != "nameFirst" ) ) 
{
    $orderby = "nameLast"; // or whatever default you choose
}

// get results from database 
$result = mysql_query("SELECT * FROM mytable ORDER BY $orderby ")  
                or die(mysql_error());   

... rest the same ...