For the start I can give you some tips.
Use your GetItemCountMethod to determine how many paging links you need to generate
int linkCount = GetItemCount() / pageSize;
Use the above linkCount to generate the paging link and display them on the page wherever you want(mostly at the bottom of the gridview.
LinkButtton[] links = new LinkButton[linkCount]
for(int i = 0; i < linkCount; i++)
{
links[i] = new LinkButton();
link[i].Text = "Page " + (i + 1).ToString();
link[i].ID = "Page " + (i + 1).ToString();
somePlaceHolderOnYourPage.Controls.Add(link[i]);
link[i].Click += GridViewPaging;
}
Now in the GridViewPaging event handler call the BindGridView with appropriate parameter.
public void GridViewPaging(object sender, EventArgs e)
{
LinkButton link = (LinkButton)sender;
int pageNumber = int.Parse(link.ID.SubString(4));
BindGridView(pageNumber, pageSize);
}
This code is just to give you an idea. This is not a tested code but should work with minor modifications.
Some tips: Use stored procedure rather then creating query in the code. This way you can avoid the GetItemCount method by passing the total number of records in the output parameter of the stored procedure.