It depends on the state. In some states the Secretary of State holds the records for business entities and in others, such as Arizona, it's an organization known as the Arizona Corporation Commission.
Regardless of the state's organization that keeps the information, one of the pieces of information you will find when you look at a company's records is the "registered agent", "resident agent" or "statutory agent."
The agent, whether a person or a representative corporation, must be located within the state where business is conducted. That agent is who or what gets served with papers for a lawsuit.
Here's a good explanation at legalzoom.
A personal example that may help: I am an owner in a business that does business in Louisiana and Arizona. Our LLC is registered in Louisiana and is registered as a "foreign corporation" in Arizona. However, we are required to have a registered agent in each state. We pay a company to act as our registered agent in each state and the registered agent has a physical address in each state in which we are registered.
If someone wants to sue my company then they can look up the name of my company in either state and will find my registered agent along with the registered agent's physical address. Service to the registered agent counts as service to my company. The agent will forward to me any service which is made to them.
EDIT: if you don't known the name of the entity, i.e., the name on the door of the business does not represent the name of the company, then you need to find the "doing business as," or DBA record of the company.
I don't know what state you're in but all the states in which I've done business maintain a "Doing Business As" system that can be searched. I guess it's possible that you're in a state that doesn't maintain DBA filings or require them.
Typically, you can search either way - search by owner or search by the DBA name. Some states, such as Arizona, record DBA names at the county level. I've seen some states allow searching by address also.