I will try to answer this question beginning beyond its set time scope by including trade practices that were instituted in the late Roman/early Byzantine period and the Muslim world. In their work "Merchant Guilds, Taxation and Social Capital" they mention the following in Chapter 2.2 when analysing the medieval taxation on trade:
From at least the third century onwards, foreign merchants were subject to tight controls. In the Byzantine customs system, from the sixth century onwards, agents referred to as comerciarii were responsible for the apotheke (‘customs houses’ or ‘commercial hostels’), where imported goods were bought and sold, and taxes collected. Official seals were attached to merchandise to prove that the appropriate tax had been paid. Under Charlemagne, trade was restricted to specific public markets, active at particular times and locations (legitimus mercatus): royal officials collected tolls from participating merchants. In the post-Carolingian Middle Ages, when central authority was weakened and power dispersed, we nevertheless find many of the same basic features of trade taxation. Throughout
medieval Europe, rulers tried to restrict trade to public markets, including a multitude of official fairs, to ensure taxes could be collected. Tolls were collected at coastal ports as well as
river and road toll stations, and mountain passes.
But what exactly did that mean for travelling merchants of that period? I checked with another source "Early medieval port customs, tolls and
controls on foreign trade" which goes into more detail on how foreign merchants were expected to behave in eastern Mediterranean ports (bear with me long quote incoming):
By the late fourth century, the comites commerciorum had overall
responsibility for the collection of customs and for commercial relations
with foreigners at least in the frontier provinces of the eastern empire
including Illyricum... The comes commerciorum controlled the importation and sale of luxury goods like silk,
and key categories of goods like weapons, wheat, salt, iron, gold, wine
and olive oil were forbidden from export. Foreign merchants could not
leave the controlled towns without permission. Anyone who offered
them lodging without the knowledge of the comes risked exile and the
confiscation of their goods. This rule suggests that foreign traders were
probably formally registered and their hostels or lodging places known
to the local representatives of the comes... During the sixth century, and especially under Justinian, the Byzantine
customs system seems to have been overhauled and local comerciarii begin
to appear and effectively take over a central role in the management of
foreign traders. The comerciarii were responsible for the customs houses (often
called apotheke in the late seventh and eighth centuries) in major ports and
markets. The apotheke and similar institutions in fact combined several
functions and are perhaps better described for convenience as ‘customs
depots’ or ‘commercial hostels’. They served as warehouses and presumably
lodging houses for foreign travellers and traders who stayed with their
goods in the interests of security and protection. More importantly, the
commercial hostels were the places where imported goods were bought
and sold and taxes collected under the control of the commerciarii. Seals
bearing the names of the commerciarii and/or the district or location of
the commercial hostel were attached to packs and bundles of merchandise
as proof that the appropriate customs procedures had been followed
and the taxes collected. In the ports, the commercial hostels were often
located on the quays, and foreign traders were probably restricted from leaving the port zone or jurisdiction until the correct taxes had been
paid and express permission had been granted by state customs officials... Muslim rulers and administrators
used funduqs [a standard term for hostels] as loci for taxing mercantile
transactions, controlling the storage and distribution of certain goods
and, in some cases, regulating the movement of particular groups of
merchants. Funduqs like the apothekai were also in effect markets or
trading exchanges where buying and selling took place. Commercial
hostels were common in the Mediterranean and the Middle East, and
similar institutions are found in the Far East. It was a universally
effective way in conjunction with toll regulations for states to manage
foreign traders in the late Roman and early medieval periods.
How did this affect Western Europe? In the next segment of "Early medieval port customs, tolls and
controls on foreign trade" some examples are expanded:
In 750 the Lombard king, Aistulf, insisted that no one could travel
by land or ship for business without a written safe conduct (epistola) or
authorization from a royal official. In a similar vein, when restoring
the border toll stations in the Alpine passes (the clusae), the king
ordered foreign and local merchants not to enter or leave his territory
without royal permission... In 823, Lothar I forbade merchants from trading outside public or officially recognized sea ports (portura legitima) in
Frankish Italy because of problems caused by toll evasion.
Later, in Europe we encounter the emergence of guilds, especially in the time period of the question. At first merchant guilds handled trade and gradually, during the 13th and 14th century, local craft guilds replaced them. The formation of guilds is when it gets tough to be a travelling merchant. Again from section 2.1.1 of the "Merchant Guilds, Taxation and Social Capital":
The privileges granted to local merchant guilds in many medieval European cities meant
that alien merchants could be either excluded from trade, or allowed to trade only subject to
a number of restrictions clearly intended to favor local merchants. Among the most common
of these restrictions were "staple" rights and brokerage rights. Local guilds’ “rights of staple”
meant that alien merchants had to bring their merchandise to municipal warehouses where
members of the local merchant guild could buy them at favorable prices. Local guilds’ brokerage
rights meant that alien merchants could not trade directly with consumers or with other alien
merchants: they had to use members of the local merchant guild as intermediaries (brokers)... Local merchant guilds also restricted access to towns: “Outsiders might enter and leave the
town for purposes of wholesale trading only and for only a limited number of days, varying from
place to place to between 14 and 40”. At the same time, local merchant guilds could exclude
from trade local individuals who were not members of the guild.
An example of this are the famous Champagne Fairs:
Fairs are distinguished by merchants buying and selling with each other more than selling to customers, and (especially) by their legal privileges: their own laws, their own courts, and special legal protection for travelers. The fairs had their own officers: two wardens (executives of the laws of the fairs); a chancellor and court officers (lawyers, agents, notaries, etc.); a police force (by 1317, 140 strong); and a host of brokers, couriers, and messengers serving the fair population at large. Merchants from distant regions began to form organized companies, that traveled to the fairs together, and lodged and worked together while they were there. These companies also had their officers: captains, in overall charge; consuls, to represent members to the officials of the fair; and harbingers, to arrive early and supervise set-up.
Therefore, instead of trying to keep track of foreign merchants, rulers restricted their access to the market placing the guilds in the middle. The guilds then would pay the taxes to the local ruler or pay a certain amount when called upon or at the end of the fiscal year. However, tax evasion was commonplace and trade taxation wasn't and couldn't be effective. In the "The Lay Subsidies and the Distribution of Wealth in Medieval England, 1275-1334" the following is brought as an example of tax evasion by local merchants:
Michaelmas (note: also known as the Feast of Saints Michael, Gabriel, and Raphael, the Feast of the Archangels, or the Feast of Saint Michael and All Angels is a Christian festival observed in some Western liturgical calendars on 29 September) was chosen as the date for the valuations in order to include the agricultural harvest for the whole year
before it was dispersed, whereas urban craftsmen and merchants were taxed
only on the stocks they held at that time... It
was also easy for merchants to avoid taxation by arranging for their warehouses to be empty by that time.
