In most stores it's quasi-contractual in that you enter the store as a "licensee" subject to the terms of that license. Many stores, especially in urban areas or stores that are very busy, will have a notice or some sort of sign that says something to the effect of "we reserve the right to have you check (stow) your bag while shopping, or to search your bag before you leave".
When a customer enters a store, they do so under a licence. So long as the store has some sort of notice, retailers are able to search any bags, parcels (i.e.. bags from other stores), or other items (people often shoplift and store small but valuable stolen merchandise in a cup with a lid and straw); they can typically (with signage) search anything that may potentially be used to shoplift, however, retailers must display a notice that your entry subjects you to this right. It's supposed to be prominent, but that is subjective. It's typically somewhere near entry and the check-out.
When a bag search is conducted no items are supposed to be opened; the retailer is supposed to only look at the contents. Customers do retain the right to refuse to have their bag searched, but since a customer enters a store under licence, the retailer also has the right to ask a person to leave, revoking the licence and often banning them forever.
If a store has a reasonable belief that a patron has stolen something, or some other property offence has been committed, they can legally detain or search a customer. This is a slippery slope for retailers though, because if they are wrong and a customer has not stolen anything, the retailer may face an action of false imprisonment, assault and a host of other torts. Most retailers will have their security ask the person to wait for the police to come, and if they refuse, they will call the police while following the person who has left with their unsorted bag.