Hmm..You might be able to output the "Please Wait Message..." and then have a javascript handler execute when the page is done loading, and modify the html (eg. modify the visible attribute).
On the PHP side, you don't really need to do anything special except to flush the output buffer before doing your search so that the browser sees the initial html.
Unfortunately, I think different browsers handle partially loaded pages differently....
An alternative is to have the PHP script display the "Please Wait" HTML along with a page fresh header so that it reloads the page.
On the PHP side, stuff the search results into a session variable.
When the search is done, the page being constantly re-loaded checks the session, sees its done, and displays the results!
This has the side effect of slowing ALL PHP requests down for that particular session cuz it reads the session data in for every request. Thus, it would be good to flush the session data when you're done with it.