aca dejo el paginador que uso yo y solo falta poner tu busqueda dentro del paginador esto te funcionara suerte
<!-- aquí comienza el listado -->
<%
'================================================= =======
Dim oConn, rs, SQL
Dim PaginaActual
Dim PaginasTotales
Dim TamPagina
Dim CuantosRegistros
TamPagina = 20 'Nº DE REGISTRO POR PAGINA
if Request.Querystring("pagina") = "" then PaginaActual = 1 else PaginaActual = Cint(Request.Querystring("pagina"))
set oConn=Server.CreateObject("ADODB.Connection")
set rs=Server.CreateObject("ADODB.Recordset")
oConn.Open MM_conn_STRING
SQL = "SELECT * FROM TABLA"
rs.PageSize = TamPagina
rs.CacheSize = TamPagina
rs.Open SQL, oConn, 1, 2
PaginasTotales = rs.PageCount
if PaginaActual < 1 then PaginaActual = 1
if PaginaActual > PaginasTotales then PaginaActual = PaginasTotales
if PaginasTotales=0 then
textotd = "No se encontraron resultados."
else
rs.AbsolutePage = PaginaActual
textotd = "Pagina " & PaginaActual & " de " & PaginasTotales
'================================================= =======
%>
<table width="100%" border="0" cellspacing="0" cellpadding="3" id="t1" class="sortable">
<tr<%= StBarras %>>
</tr>
<% Do While Not Rs.EOF AND CuantosRegistros < TamPagina %>
<tr<%= StColor %>>
</tr>
<% CuantosRegistros=CuantosRegistros + 1
Rs.MoveNext
loop %>
</table>
<%
end if
rs.Close
oConn.Close
set rs = nothing
set oConn = nothing
Response.Write("<hr size=""1"">**")
if PaginaActual > 2 then Response.Write("<A HREF=?pagina="& 1 &">Primera Pagina</A>*|*") Else Response.Write("<font color=""#CCCCCC"">Primera Pagina</font>*|*")
if PaginaActual > 1 then Response.Write("<A HREF=?pagina="& PaginaActual-1 &">"&TamPagina&" Anteriores</A>*|*") Else Response.Write("<font color=""#CCCCCC"">"&TamPagina&" Anteriores</font>*|*")
if PaginaActual < PaginasTotales then Response.Write("<A HREF=?pagina=" & PaginaActual+1 &">"&TamPagina&" Siguientes</A>*|*") Else Response.Write("<font color=""#CCCCCC"">"&TamPagina&" Siguientes</font>*|*")
if PaginaActual + 1 < PaginasTotales then Response.Write("<A HREF=?pagina=" & PaginasTotales &">Ultima Pagina</A>") Else Response.Write("<font color=""#CCCCCC"">Ultima Pagina</font>")
%>
<!-- aquí termina el listado -->