I'm planning on stopping in to Sault Ste Marie on a bus trip. The Indian Trails (long distance) bus stop is an hour walk outside of the downtown on the Michigan side and there's a similar situation on the Ontario side (though it's possible to get the the Greyhound bus stop by city bus on that side). The bus across the border runs between the downtowns. So I know I'm already in for a lot of walking, is there a place to store my bag while I explore either of the downtowns?
Speaking broadly, it is very hard to come by public lockers or other short-term options anywhere in the U.S., compared to Europe or Japan. Their elimination has been going on for some time, starting with concerns over illegal drugs and then terrorism— and fear of the associated legal liabilities. There are a few left luggage or "parcel check" services in touristy areas and in larger cities, but as far as I can tell, none exist in Sault Ste. Marie, and the only place where I'd expect to find one, the Eastern Upper Peninsula Transportation Authority building where the Indian Trails bus stop is, does not appear to be a public facility.
I think you have two main storage options:
Rent a car, and store your bags in the trunk. There are several agencies in downtown Sault Ste. Marie, and some may even be willing to pick you up from EUPTA. Since bag storage at an airport or train station runs anywhere from $5 (e.g. various Amtrak stations) to $35 (e.g. San Francisco International Airport) per day per bag, the cost of a rental car is not so bad, especially since it gives you additional options to explore and saves you an hour's walk down a boring industrial access road. (Google Street View on the road from EUPTA to downtown looks pretty dismal).
Ask a hotel if they will accept your bag, though this can be tricky. In a big hotel in a big city, the bellhops don't really care if you are a guest; in a B&B in a small town, you might rely on the kind-heartedness of the proprietor; but in mid-sized chain hotels, it is likely the staff will be unwilling to accept bags from anyone other than their registered guests. You might try calling around to see if there are any takers.
Just to report back what I found: There is no place to store a bag on the Michigan side though there are several hotels I didn't try. There were indeed lockers inside the Station Mall on the Ontario side.