The few examples of sorting an SPGridView I have found use a DataSet which then allows you to use a DataView to sort the contents of the SPGridView.

I am using a CAML query as my data source so this is not possible, instead I pass the sort expression and sort direction to the query and handle the sorting that way.

First of all I create a sorting event and add this to the SPGridView - credit for this code goes to ElPowlo :

void _gvProducts_Sorting(object sender, GridViewSortEventArgs e)
        {
            string lastExpression = "";
            if (ViewState["SortExpression"] != null)
                lastExpression = ViewState["SortExpression"].ToString();

            string lastDirection = "asc";
            if (ViewState["SortDirection"] != null)
                lastDirection = ViewState["SortDirection"].ToString();

            string newDirection = "asc";
            if (e.SortExpression == lastExpression)
                newDirection = (lastDirection == "asc") ? "desc" : "asc";

            ViewState["SortExpression"] = e.SortExpression;
            ViewState["SortDirection"] = newDirection;

            PopulateSPGridView(e.SortExpression, newDirection);
        }

I then populate my SPGridView using the sort criteria - in my real world project I also pass some values to filter the SPGridView but these have been left out here:

      void PopulateSPGridView(string strSortExpression, string strSortDirection)
        {
            sdsProducts = new SPDataSource();
            SPList oList = site.Lists["Pages"];
            sdsProducts.List = oList;
            sdsProducts.DataSourceMode = SPDataSourceMode.List;                     
            string strSortDirectionBool = "";

            //Convert asc and desc to True and False for use in the CAML query

            if(strSortDirection == "asc")
            {
                strSortDirectionBool = "True";
            }
            else
            {
                strSortDirectionBool = "False";
            }

                        sdsProducts.SelectCommand = "<ViewFields><FieldRef Name='Product_x0020_ID' /><FieldRef Name='Title' />"
               + "<FieldRef Name='Brand' /><FieldRef Name='Chemistry' />"
               + "</ViewFields><Query><OrderBy><FieldRef Name='" + strSortExpression + "' Ascending='" + strSortDirectionBool + "' /></OrderBy></Query>";
                      
            _gvProducts.DataSource = sdsProducts;
          
            _gvProducts.DataBind();
            
        }

For more information on CAML queries and a useful CAML Query Builder have a look at Patrick Tissegham's U2U site