You could have a totally free market, in which independent organizations certify particular restaurants as "safe", but then the customers would have to constantly be checking those certifications.
In the US state where I live, that's what we have with government regulations, and I suspect that's what we would privately develop without them.
It's not at all a big deal, and it's actually pretty cool.
Health inspectors come at random times to each restaurant, and the restaurants are required to PUBLICLY POST THEIR REPORTS in the restaurant itself.
The result is that people read these reports, really! Folks shy away from going to restaurants with lower scores, and the fact that a place has a high score is something that will invariably come up in conversations. It's not some goofy thing that only a few people do, it's something that people notice and then talk about if the score is particularly high or low.
(Just a few days ago I went back to a place for the first time in a year since they got a bad score--82, a score which of course included written notes on all the problems found. Now their score is 100, which is really unusual, and I won't be hesitant to go back for cleanliness reasons. These scores make a real difference in people's behavior.)
I know that in some US states that these reports aren't published the same way, so people can't make decisions on whether to eat somewhere based on the problems found in the previous inspection.
Given that the existence of government testing will in practical terms preclude the development of private testing in most areas, if you don't have real-world transparency in the testing process that the state government provides/enforces, then people will just become used to the fact that the information isn't there, and possibly just assume that it's too much information for individuals to keep up with or even pay attention to anyway.
But if you're used to seeing these results, it's a natural thing to look for the posted health report. It's as natural a thing as to look for as credit card logos, or noting whether this is a place where you pay your bill at a cashier up front versus paying at the table. You really just do it and don't think much of it.
Well, unless you're writing a reply to a slashdot comment. :-)
For a different industry, look at the history of Underwriter's Laboratories. Before their existence, there were neither private nor governmental regulations on the safety of electrical devices. Since unsafe devices were being sold and causing homes and businesses to burn, insurance companies that bore the brunt of the financial side of the resulting losses got together to make their own private testing agency, and arranged their policies to encourage the use of only UL-tested and certified electrical devices.
The market was allowed to work in that case, in that it was allowed to develop private certification agencies that people and companies do pay attention to. While technically it's possible to buy and sell non-UL tested devices even today, for the most part you'll not find them in stores as stores won't sell them as a mass-market item at all, and if you did buy such a product you'd have insurance problems if/when they caused a fire, and you'd probably have liability problems if you actually used them in a business.
You'd pretty much have to go out of your way to purchase something like this today, meaning that you'd be doing so only if you had a real reason to, (maybe you're stripping the device for parts, or comparing something between multiple devices of the same type, working on things in your own electronics lab and the like.)
In any event, government fortunately happened not to try to develop it's own system of electronic safety certification that would preempt the development of private certification, so we have a working private system that can pay attention to the actual real safety issues, and get less bogged down in politics.
Of course, their are real costs of both systems, and nothing will ever be completely perfect. (For instance, in the UL case, one of the reasons you have all these wall warts is that they are separately certified, and it's easier for electronic manufacturers to use some standard part that's more tested as opposed to integrating that into, say an xbox directly, and then needing to pay and wait for the full thing to be tested and shown to meet all the requirements of having everything integrated together.)
But at least a private system can develop based on a negative feedback loop based on actual economics of safety issues, (ie, companies will lose money and go out of business as unsafe products are used, and this process will happen whether it's an election year or not, and whether there's public fanfare about some problem or not.)
I would prefer that these sorts of things develop privately, and be allowed to develop privately, and I don't think that this really requires the end consumers to be all-knowing PhD-holders in every field. :)