For example, if someone is in the business of charging other people to do patent searches for them, are there laws that mandate how the search must be performed? For example, the business must search in a similar manner to the examiner would or that they must be at least as thorough as the examiner would, etc.
No. It could be something negotiable. Will they use the USPTO's West or East systems in the USPTO Public Search Room? Will they specifically look in non-patent literature?
At one time there was a (horrible) path to accelerate examination that involved a search as-specified by the USPTO, then an argument as to why the application was patentable over everything you found. It is no longer in effect but you could locate the search specification and contract for that very expensive search.