lieserlさんのレスに追記として(汗
検索条件などはQueryStringでURLに埋め込むかセッションで持ち回るかのどちらにするかを決めておいてください。フォームが使えないのでhiddenというわけにはいきませんので(絶対に使えないわけじゃないけど、ページ番号をanchor要素にするとJavaScriptとかのお世話にならないといけないので避けたい)。GoogleなどはQueryStringでの持ち回りですね。
#ページ遷移している途中で件数が変わったりするのもGoogleならではですが(汗
表示開始するレコードまでにスキップする件数(最初は0)を、2ページ目以降は(ページ番号-1)×(1ページあたりの表示数)としてQueryStringで渡します。ページ番号のanchor要素にスクリプトで付与します。何ページ分のデータがあるかは検索条件で
count(*)を取得すればいいでしょう(実際の表示用の取得時はlimitで表示する分だけ取得)。これもGoogleはstart=n(nは0,10,20,30・・と表示数の倍数)といった形になっています。
渡されたスキップ数(渡されなければ「0」)から、今から表示するページのページ番号は(スキップ数/表示数)+1で求められます。あとはlieserlさんのレスを参考に前後どこまで表示すればいいかを算出してください。
このあたりのロジックは、ページあたりスレッド数が固定の掲示板などでも同様の処理を書くハズなので、一度キチンと作っておくと使い回しが効きます(というかロジックが自然に出てきます)。管理画面でデータ編集するようなときでも一覧表示から選択なんてときは前後のページへのリンクとか使いますしね。

GETのままでは検索エンジンのロボットが拾ってくれなかったためにSEO対策として有効だと言われていますね。