hola
bueno, pues necesitas 3 cosas
0. al titulo de cada columna agregarle un href que vaya a la misma página que se esta visualizando, y que envie dos parametro llamados por ej $field y $order de este modo
http://url?field=id&order=desc (order sera ASC o DESC y field debe ser el nombre de cada columna coincidente con el mismo nombre que tiene el campo en la base de datos)
1. a la consulta agregarle un "order by $_GET['field'] $_GET['order']"
2. validar que si no se ha obtenido nada en $_GET['field'] ni en $_GET['order'] le asigne a estas valores por defecto. y en caso contrario pues que use los valores que lleguen
y con esto debe funcionarte (espero que tengas conocimientos básicos de validación)
prueba y comentas
saludos