Hi adambswa,
Please take reference the below code and correct your code.
Database
For this sample I have used of NorthWind database that you can download using the link given below.
Download Northwind Database
HTML
Name :
<asp:TextBox ID="txtSearch" runat="server"></asp:TextBox>
<asp:Button ID="btnSearch" runat="server" OnClick="Search" Text="Search" />
<asp:GridView ID="gvCustomers" runat="server" AutoGenerateColumns="false" AllowPaging="true"
    AllowSorting="true" OnSorting="OnSorting" OnPageIndexChanging="OnPageIndexChanging"
    PageSize="10">
    <Columns>
        <asp:TemplateField HeaderText="CustomerID" SortExpression="CustomerID">
            <ItemTemplate>
                <%# Eval("CustomerID")%>
            </ItemTemplate>
        </asp:TemplateField>
        <asp:BoundField DataField="ContactName" HeaderText="ContactName" SortExpression="ContactName" />
        <asp:BoundField DataField="City" HeaderText="City" SortExpression="City" />
        <asp:BoundField DataField="Country" HeaderText="Country" SortExpression="Country" />
    </Columns>
</asp:GridView>
Namespaces
C#
using System.Data;
using System.Data.SqlClient;
using System.Configuration;
VB.Net
Imports System.Data.SqlClient
Imports System.Data
Code
C#
private string SortDirection
{
    get { return ViewState["SortDirection"] != null ? ViewState["SortDirection"].ToString() : "ASC"; }
    set { ViewState["SortDirection"] = value; }
}
protected void Page_Load(object sender, EventArgs e)
{
    if (!this.IsPostBack)
    {
        this.BindGrid();
    }
}
private void BindGrid(string sortExpression = null, string searchText = null)
{
    string query = "SELECT CustomerId, ContactName, City, Country FROM Customers";
    string constr = ConfigurationManager.ConnectionStrings["Constring"].ConnectionString;
    using (SqlConnection con = new SqlConnection(constr))
    {
        using (SqlCommand cmd = new SqlCommand())
        {
            if (!string.IsNullOrEmpty(searchText))
            {
                query += " WHERE ContactName LIKE @ContactName + '%'";
                cmd.Parameters.AddWithValue("@ContactName", searchText);
            }
            using (SqlDataAdapter sda = new SqlDataAdapter())
            {
                cmd.CommandText = query;
                cmd.Connection = con;
                sda.SelectCommand = cmd;
                using (DataTable dt = new DataTable())
                {
                    sda.Fill(dt);
                    if (sortExpression != null)
                    {
                        DataView dv = dt.AsDataView();
                        this.SortDirection = this.SortDirection == "ASC" ? "DESC" : "ASC";
                        dv.Sort = sortExpression + " " + this.SortDirection;
                        this.gvCustomers.DataSource = dv;
                    }
                    else
                    {
                      this.gvCustomers.DataSource = dt;
                    }
                    this.gvCustomers.DataBind();
                }
            }
        }
    }
}
protected void Search(object sender, EventArgs e)
{
    this.BindGrid(null, txtSearch.Text);
}
protected void OnPageIndexChanging(object sender, GridViewPageEventArgs e)
{
   this.gvCustomers.PageIndex = e.NewPageIndex;
    this.BindGrid(null, txtSearch.Text);
}
protected void OnSorting(object sender, GridViewSortEventArgs e)
{
    this.BindGrid(e.SortExpression, txtSearch.Text);
}
VB.Net
    Private Property SortDirection As String
        Get
            Return If(ViewState("SortDirection") IsNot Nothing, ViewState("SortDirection").ToString(), "ASC")
        End Get
        Set(ByVal value As String)
            ViewState("SortDirection") = value
        End Set
    End Property
    Protected Sub Page_Load(ByVal sender As Object, ByVal e As EventArgs) Handles Me.Load
        If Not Me.IsPostBack Then
            Me.BindGrid()
        End If
    End Sub
    Private Sub BindGrid(Optional ByVal sortExpression As String = Nothing, Optional ByVal searchText As String = Nothing)
        Dim query As String = "SELECT CustomerId, ContactName, City, Country FROM Customers"
        Dim constr As String = ConfigurationManager.ConnectionStrings("Constring").ConnectionString
        Using con As SqlConnection = New SqlConnection(constr)
            Using cmd As SqlCommand = New SqlCommand()
                If Not String.IsNullOrEmpty(searchText) Then
                    query += " WHERE ContactName LIKE @ContactName + '%'"
                    cmd.Parameters.AddWithValue("@ContactName", searchText)
                End If
                Using sda As SqlDataAdapter = New SqlDataAdapter()
                    cmd.CommandText = query
                    cmd.Connection = con
                    sda.SelectCommand = cmd
                    Using dt As DataTable = New DataTable()
                        sda.Fill(dt)
                        If sortExpression IsNot Nothing Then
                            Dim dv As DataView = dt.AsDataView()
                            Me.SortDirection = If(Me.SortDirection = "ASC", "DESC", "ASC")
                            dv.Sort = sortExpression & " " & Me.SortDirection
                            Me.gvCustomers.DataSource = dv
                        Else
                            Me.gvCustomers.DataSource = dt
                        End If
                        Me.gvCustomers.DataBind()
                    End Using
                End Using
            End Using
        End Using
    End Sub
    Protected Sub Search(ByVal sender As Object, ByVal e As EventArgs)
        Me.BindGrid(Nothing, txtSearch.Text)
    End Sub
    Protected Sub OnPageIndexChanging(ByVal sender As Object, ByVal e As GridViewPageEventArgs)
        Me.gvCustomers.PageIndex = e.NewPageIndex
        Me.BindGrid(Nothing, txtSearch.Text)
    End Sub
    Protected Sub OnSorting(ByVal sender As Object, ByVal e As GridViewSortEventArgs)
        Me.BindGrid(e.SortExpression, txtSearch.Text)
    End Sub
Screenshot
