How were laws promulgated in the Middle Ages?

That was part of the function of the Town Crier.

The office (office as it was an official position) can be traced back - in England at least, to at least 1066 as the Bayeux Tapestry depicts two "Bellmen" (another name for the same office), for source see here. They were protected by law as they had to announce tax increases - always a popular subject :) as well as other proclamations, news and even advertising - for which they had to be paid.

Another reference here also names the two earliest known criers from 1395.

Sometimes a crier - usually at the beginning of a carnival (a local town celebration) can be heard crying "Hear Ye, Hear Ye, Hear Ye" but the original cry was "Oyez, Oyez, Oyez" as referenced in the second reference.

There is reference here to the activity of criers before medieval times and the word "stentorian" ie loud voice may be due to a Greek warrior in the Trojan wars called Stentor.

As noted by Semaphore:

..., apart from the Common Law in England, there was also the Landrecht in Germany, the Visigothic Code in Hispania, the coutume in France, the Code of Justinian in the Byzantine Empire, the Russkaya Pravda in Russia, and all preceded by tribal laws and Roman law from region to region.

Although I only comment below to the English Common Law practice, the Anglo-Saxon traditions underpinning it originated from the North Sea coasts of Friesland and Jutland. Contemporary traditions in those areas were undoubtedly similar to start; and then evolved according to variant circumstances.

Class notes on Description and History of Common Law provides a brief history of the initial devlopment of a centralized Common Law following the Norman Conquest:

The Norman Conquest

By virtue of having conquered England, William the First was able to proclaim that all land and land-based rights, including those of keeping court, were now vested in the king. Through this redistribution of land and the consolidation of all rights and relationships associated with land tenure under the crown, local courts eventually came under the administration of Norman rule,

Court keeping rights were still granted concerning land tenure, However, all courts had to he conducted in accordance with the king's interests, particularly his monetary interests. Thus, judicial decision-making was slowly being transformed into the function of an increasingly bureaucratic system of justice.

The king's interest in assuring a proper flow of justice-profits into the royal treasury brought about the institution of the eyre. Developed in the twelfth century as a powerful force for centralizing control over local courts, the eyre provided the structural basis for the development of a common law for England. It consisted of four itinerant judges representing the king who would periodically examine the activities of the county and hundred courts.

In The Jury and the English Low of Homicide, 1200-1600, T. A. Green recaps both the specified period and its Anglo-Saxon & Norman precedents (pp 416-7):

This distinction between slaying by stealth and slaying openly and of a sudden was embedded in Anglo-Saxon criminal law and survived after the Conquest at least until the middle of the twelfth century. Capital punishment was reserved for only the former. Though little is known about the exact scope of "slaying by stealth," it surely included killing by poison and possibly by ambush or other forms of surprise attack. These were "botless," or unemendable crimes; that is, they could not be remedied through the payment of compensation (bot) by the slayer or his kin to the kin of the slain.

With the exception of these unemendable homicides, or "murders," slaying was a matter for compensation. The rules governing compensation were, within a century of the Anglo-Saxon invasion of England, already embodied in the dooms, "legislation" declaring social custom. The earliest dooms merely recorded the levels of compensation; later dooms established the local pretrial and trial procedures required before compensation could be adjudged in a given case.' Failure to stand to justice or, thereafter, to pay the required sum gave the slain person's kin the right to prosecute the feud and even to take the life of the slayer. But it is likely that most slayings led to "composition," payment and re-establishment of relative harmony between kin groups.

Later he recaps the manner in which initial investigation of homicides was performed, and the subsequent proceedings. (pp 422)

A review of the procedures involved from the time of the slaying until the final resolution of the case reveals the manner in which such community sentiment might be expressed. In all homicide cases, the coroner, a Crown official at the county level, was required to hold an inquest as soon as possible. ° Usually within a day or two of the discovery of the body, the coroner assembled the inquest jury, composed of representatives of the village in which the slaying occurred and of several neighboring villages, and conducted the inquest. He there noted the cause of death, took down the names of suspects mentioned by the jurors, and ordered the sheriff or hundred bailiff to arrest the suspect if this had not already been done. The suspect was held for trial before the royal justices, whose circuits or "eyres" were held infrequently throughout the thirteenth century. From early in the fourteenth century, the itinerant royal justices came twice yearly to the county town for delivery of its gaol. A record of the coroner's inquest was available to the court, as was the record of any presentment made either before the royal justices or before the justices of the peace.

It is clear from these excerpts, as well as the remainder of this excellent paper, that not only were the basic laws well understood, the proper proceedings to be performed after a violation were as well. As today, there were specialized societal roles - Sheriffs, Coroners, Lawyers, and Judges - tasked with expert knowledge in various aspects of the Law. Every county seat would be visited twice yearly for an assize by appointed Justices, to deal with all pending cases.

Additionally, there was a fundamental understanding of many consequences of the existing Laws that were well understood by the populace at large. (pp 424-5)

It is clear that the trial jury possessed the power to state the verdict in a form that compelled the judgment it believed the defendant deserved. The jury could produce a verdict of clear-cut malicious homicide; it could absolve the defendant of all liability by stating either that he had not committed the act or that he had committed it in the course of taking a felon; it could state that the defendant slew by accident or in self-defense. The jury's choice of verdict, its concept of the defendant's liability, did not have to square with the formal rules of the law. Even if the bench suspected that juries took advantage of their evidence-gathering role in this way, the justices had no means in any given case for getting behind the jury's formulistic verdict to the truth of the matter.

This hold true right up until the Tudor reformation of the Law, where our modern concept of an impartial jury replaces the earlier medieval* jury composed from informed witnesses.

Few of us today actually know the details of the laws that we are assumed to know, and to follow. The experts who do are Lawyers and their Clerks. When we have questions, we seek their advice. It was no different 800 years ago in England - except the fees were a bit less.

Update - The Angevin Law Reform ~ 1180 (my emphasis)

The legal distinction between these two types of homicide was obliterated in the course of the reforms of Henry 1[ (1154-1189). Whatever the real ends of monarchical policy - deterrence, financial gain, or political centralization - the Angevin reform of the criminal law established a system of substantive law that was sharply at odds with prevailing social practices. The sudden twelfth-century growth in royal criminal law, in theory implementing the ancient royal obligation to enforce the king's peace throughout the land, was principally a jurisdictional development. Henry II effected this development by ordering his justices to ride circuit and his local officials to produce before those justices good and loyal men of the county who had knowledge of recent felonies and other, lesser, breaches of the king's peace.

As for the promulgation of these new laws, Parish Life in Medieval England notes (Thank you sempaiscuba):

Then, it was in the church that all laws, civil as well as ecclesiastical, were published. Here, too, notice of all manner of civil proceedings was made.

I will give a partial answer, focusing on Sweden ca 1250-1350, but this should be indicative of much of "germanic" Europe up until that point, in particular Scandinavia.

Simply put, promulgation was not separated from approval, and approval was done using the same system that also ensured that it was followed: the thing. We should first note that there were several different things, from the lowest level (in Sweden härad or hundare, hundred), which were held with some regularity, but from every week to twice a year, depending on which part of the country, up to the large, county-level things. The things were not only legal gatherings, but also market days and a general gathering, so they were likely well visited.

It should be noted here that in the start of the period, each county had it's own set of laws, which had similarities but were clearly distinct. The central thing was led by a lawspeaker, who was responsible for both stating an helping interpreting the law as well as leading the thing. Over the period, the local laws grew more uniform, and at the end of it there were only two sets: one for countryside, and one for cities.

This process was done through the thing: for the law to be changed, every local thing would have to discuss and ultimately accept the changes. To ensure this, changes were often prepared by a small committee made up of the lawspeaker, the bishop, and local magnates.

Sources

Dick Harrison: Jarlens sekel discusses mostly the organisation ca 1250, and the earliest attempts at uniform laws in a few areas. Michael Nordberg: I kung Magnus tid covers the end of the period.

Pieter covered England. I'll give a short explanation of how it worked in France.

When passed, laws were sent in writing to the district courts, or parlements.

The kings issued laws and sent them to their parlements to be registered, in order to bring the new legislation to public attention and to make it enforceable within the parlements’ jurisdictions. Reduced to its essentials, registration meant that the parlements ‘published’ the laws by reading them aloud in open court, copied them into folio registers and sent them in printed form to subordinate lawcourts.

But the parlements claimed that registration involved more than this minimalist procedure. They argued that in registering the laws, they also validated them, bestowing a seal of approval and conferring public standing.

LOUIS XIV and the PARLEMENTS - by J Hurt - ‎2002

Unlike England, regional law courts in France were effectively able to veto new laws by refusing to promulgate them.

This made it impossible to reform France, and was the proximate cause of the French Revolution: Louis XVI was unable to enact his tax reforms and rescue the public finances, because the parlements would not let him. IOW, France's absolute monarchy wasn't nearly absolute enough.