Common disclaimer - The "medieval period" is very fuzzy, how long it was depends on where you look and how you define it and I know jack shit about history outside of Europe. We good? Good.

That depends on who you are and where you are going of course. Keep in mind that most people did not travel long distances for leisure purposes. So, if you travel somewhere far from home it's usually for a reason. Merchants travel to transport their goods (although usually by boat where available), officers traveled a fair bit for their work and people who were some form of politicians or nobles traveled a fair bit out of necessity. The average medieval burger or farmer however did not generally travel frequently or far.

Why does this matter? Because people like officers, merchants and politicians and nobles usually have a very specific purpose in mind and that purpose is usually connected to a host. That is, they're traveling to meet someone. Usually they would board their horses with their host. Military facilites, the upper class and merchants would usually have a stable. So if you're either of those things, odds are you'll leave your horse if the stable of your host.

But you're curious about the cases that fall outside of this norm and the answer is livery stables. They're basically a stable where you can turn your horse in and have it cared for in exchange for payment. Usually these would be found either at an inn or boarding house or sometimes on the outskirts of the city. Basically you go there, talk the the stable master and tell him what you want. He tells you the price, you pay him and the deal is done. Depending on how long you intend to leave your horse and where you are your options may have included things like full livery (the horse if fed, cared for, exercised, perhaps even trained), part livery (basically a box, food and water. This is mostly for shorter periods) or grass livery (your horse is taken to a paddock somewhere so it can graze and move freely. Usually for extended stays).

Livery stables were often more than just stables. You could have your horse reshod, fed, cared for, perhaps even have equipment repaired there. They also frequently sold feed and other equestrian equipment.

If you're only in town for a brief period you can just tie your horse to a rail, pole or ring. These would generally be available outside establishments that frequently saw mounted visitors. Sometimes there would be someone who could keep an eye on your horse available. Such as guards by city hall, a younger family member at a local business etc. Other times you left it unattended because you were only gone for a short time. Could someone steal your horse? Yes. Did it occasionally happen? Yes. However, horse theft was generally harshly punished.