There may be other options, but here is what came to my mind.  The user
is going to click a button/link to begin the search, right?  This will
submit the form or whatever.  As soon as that button is pushed, the
next page the user will see is the results from the search.  There
isn't really a way I know if to add a different page between those two,
but you can use javascript to display a message while the search takes
place.  For example, if you are submitting a form...

**** START CODE ****

<script language="javascript">
 function doBeforeSubmit()
 {
   document.getElementById("displayBeforeSubmit").style.display =
"none";
   document.getElementById("displayAfterSubmit").style.dispay =
"block";
   return true; // you must return true or the form will not submit
 }
</script>

<div id="displayBeforeSubmit">
<form action="results_page.jsp" method="post"
onsubmit="javascript:doBeforeSubmit()">
   ...
   form stuff
   ...
</form>
</div>

<div id="displayAfterSubmit">
 <h3>Searh processing.  Please wait...</h3>
</div>

**** END CODE ****

I think this should work unless the browser immediately displays the
new page (results) but leaves that page blank while it waits for the
server to process.

However, I think it would look best to use AJAX (I think that stands
for Asynchronous Javascript and XML).  The idea behind this is that you
can use only one page for everything.  It's kind of hard to explain,
but really not too hard to implement.  If you are interested, let me
know and I will explain.

I would use a servlet. The servlet could check if the search is
completed. If it's not the servlet would include a jsp with the please
wait message. This jsp should contain a meta refresh tag, pointing to
the same servlet, so that after n seconds the servlet is reloaded.
If the search is completed the servlet can redirect to another page