Search only returns results for site admins?

We have a SharePoint Online site that is exhibiting a very odd search behavior.  If a user clicks on a document library and then performs a search they get "Nothing here matches your search."  Howeve...