The WSS 3.0 search facility is a bit restricted in scope (you can only search one site collection at a time), but once it is configured correctly it should work well within that restriction.
Have you checked that your Search (Indexing) service is running properly? You will need to be a farm and/or server administrator to perform these checks.
The indexing service runs as the "Windows SharePoint Services Search" service on the web server. It is the one that populates the search database, which the user search box then refers to.
It is configured through the admin console under Operations -> Services on Server (look for the Windows SharePoint Services Search entry - you can click it to get to the configuration page).
You can also check the status of the index job through Operations -> Timer Job Status (look for the SharePoint Services Search Refresh line). If that shows a failure, you may need to check the server log (normally held in C:\Program Files\Common Files\Microsoft Shared\web server extensions\12\LOGS).
I hope this helps. Sorry if it represents troubleshooting steps you have already taken.
Post back if you discover any problems you can't solve, and I or someone else may be able to help.