bueno se puede hacer con javascript o con php, por el foro vamos con la repusta en php
en cada titulo ones
<a href="?ordenar=nombrecolumna&tipo=asc">ascendente</a> // o tambien una imagen o codigo
<a href="?ordenar=nombrecolumna&tipo=desc">ascendente </a>
luego en la consulta
mysql_query("select * from tabla order by ".$_GET['ordenar`]." ".$_GET['tipo`]);
previamente podrias comprobar los get para que traigan un valor y que sean los correctos
saludos