Giving feedback is a definitely a good practice and keeping your audience engaged is even better. You can use many solutions from the bare bone message with an animated icon to a callout in a modal window.
A few things to keep in mind:
- How many searches do you expect your users to make?
- Consider the average loading time
- Keep in mind traffic spikes
You probably won't need much if the results are displayed within a second but if it takes significantly more (booking plane tickets and the likes), then improve the UX by providing your users with some more substantial content: things to do or read.
Take a look at Response-times-3-important-limits on J.Nielsen's blog.
As an example, one of the best solution I've seen recently to capture users attention while waiting is at www.hipmunk.com but I'm sure there are many other great solutions in the booking industry.
More in-depth stats at http://blog.kissmetrics.com/loading-time - 2011
EDIT: Searching a bit returned some solid research paper on tolerable waiting time: http://cba.unl.edu/research/articles/548/download.pdf
Disclaimer: I'm providing these links as examples and I am not affiliate with Hipmunk nor with Kiss Metrics.