First of all, your site has to be indexed regularly, you can do this by either running cron manually from the admin status report page (Administer -> Reports), or by setting up cron to run on your server (see http://drupal.org/cron ).
Then there are two ways to add the interface for the users:
1. Assign the search block to any region (header, sidebar, etc.) you like. You can do this in Administer > Site building > Blocks. 2. Many themes include a search block which can be enabled via the theme configuration at Administer > Site building > Themes ... > your theme configuration.