How do I make my database public, and let people search the database?

no problem.

You will set up a Role which allows for Viewing records but not editing.  Typically you also go into Role User Interface settings and turn off everything so they just land on a stupid simple dashboards with buttons to do whatever they need to do.  i would also hide all your tables.

Then open up that Role to  "Everyone on the internet". Here is a link to help text on that.

 http://www.quickbase.com/user-assistance/Default.html#share_with_everyone_on_internet.html