A store can surely deny entrance to those with bags, unless they leave them in a designated location. This is not a search and does not implicate 4th amendment rights. I recall when I was in college many stores near the campus had such a policy, particularly bookstores.
In many US states, there is a so-called Shopkeeper's privilege. This is a common-law rule which allows a retail merchant to detain (but not search) a suspected shoplifter long enough to check the facts, and summon police. The police can then search if the evidence presented by the shopkeeper provides probable cause.
A shopkeeper can ask a suspect to consent to a search, saying that otherwise s/he will call the police.
In some US states, this privilege has been supplemented or expanded by statute. The Wikipedia article on "Shoplifting" says:
In the United States, store employees who detain suspects outside of and inside the store premises are generally granted limited powers of arrest by state law, and have the power to initiate criminal arrests or civil sanctions, or both, depending upon the policy of the retailer and the state statutes governing civil demands and civil recovery for shoplifting as reconciled with the criminal laws of the jurisdiction.
This article from ExpertLaw says:
[US] States have passed laws that permit merchants to temporarily detain shoplifting suspects while they investigate their belief that shoplifting occurred, or while waiting for the police to arrive and formally charge or arrest the suspect.
The details of the laws vary significantly, but in general these laws provide the merchant with immunity for any claim of wrongful arrest or detention as long as they do not apply any unreasonable force in order to apprehend or detain the shoplifter, and as long as the detention is reasonable in its duration.