What is the nature of fantasy?
One thing to consider before we even begin is whether or not you really want to keep medieval transportation a thing in your campaign. One thing that I'd suggest doing is making sure that your players actually are willing to play in a campaign where they don't have access to all-action, all the time. If they want a high fantasy game where the world is their oyster and they don't want to worry about transit, that's something that making a GM decision about can backfire on you for.
Although that sounds kind of harsh, there is another thing you can do while talking to your players: ask them not to use teleportation magic of their own accord. Discussing the game with them and coming to a mutual agreement that there will be no teleportation or long-distance flight for the party because that way the campaign will be more interesting and it'll achieve the original feel can be just as good as a mandate from up above. You can even mention that you don't want it "in the setting", if you're not using a setting that has explicit teleportation and so forth.
The Myth of Diminished Utility
Your spellcasters aren't going to be useless if you end the existence of transportation magic. You can always make there be an onerous spell component or limit teleportation to magical hubs if you want to give your spellcasters some utility: they'll just have to hike one way, for instance, then recall back to the town. You can even limit these fast movement spells to individuals, making it impossible to move the whole party but leaving them open to the players in the case of need.
However, when you look in the vast levels of utility that Pathfinder provides, removing these transportation spells aren't going to make as much of a difference as you thought. I saw a GM complaining about how Wind Walk ruined his campaign the other day; Pathfinder has certain elements that often get patched out in individual groups for the sake of "feel" or "cohesion", and you should feel free to invoke rule zero on this matter if you absolutely desire.
Make it Impractical
As other answers have mentioned, it's not always practical to have teleportation magic. Traveling with a large group, mounts, plentiful gear, and even having to deal with spell preparation limitations can all prevent the use of magical travel. Make their destination somewhat uncertain, and they already cannot teleport, and make it hidden by air and they basically are stuck walking. Do this right, and the players won't even realize that you're trying to restrict such workarounds.
At very high levels, it may be possible to bypass all the barriers to travel-assisting magic, but at this point most of the wear and tear of travel is effectively incidental. It's not like they'll run out of gold chartering a wagon or staying in an inn, and potentially the amount of time they have between the world going into a crisis without them means that they can only accomplish one or two objectives, even with magical travel. Remember that anything they have can also be had by their enemies, and high-level characters may have made recurring enemies that are just as (if not more) powerful as they are.