Together with bread the two basic food-stuffs.  Forget vegetables, meat, and dairy products, beer and bread are what civilization grew on.  Archaeologists, bakers, and brewers still argue about which came first, but the two are so intertwined that it really doesn't make any difference.  Both of them make use of  that wonder organism, yeast.
     Beer is essentially a beverage produced by placing any type of grain in water and letting yeast convert the sugars and starches to alcohol and carbon dioxide.  It's that simple.  Over the thousands of years that mankind has been making beer we've come up with just about every imaginable combination of ingredients and techniques.
     The Babylonians and Egyptians brewed beers using wheat and barley.  In Europe brewers added oats and rye to the repertoire.  Soon after man learned to make beer he learned to malt the grains.  Malting is a process where grains are allowed to sprout and then dried in an oven.  This process produces enzymes which enable the yeast to consume starches and improves the flavor of beer.  Lightly toasted grains produce a lighter colored beer and heavily toasted grains produce a darker beer.  He also learned to add flavoring to his beers.  These flavorings were often bitter herbs, bitter because that counteracted the sweetness of the fermented mix.  But mankind being who we are, all sorts of herbs and mixtures of herbs were added.
 By the Middle Ages mixtures of herbs were being referred to as 'gruit'.  Each brewer had a particular mixture of herbs that went into his gruit, and these mixtures were closely guarded secrets.  In some areas the church had a monopoly on producing gruit and required all brewers to purchase it from them.  Hops, the bitter herb that gives modern beer its distinctive taste, was known to and used by brewers throughout the history of beer.  It wasn't until the 12th or 13th Century that it first came into widespread use, primarily in Germany.  From this point on we must make the distinction between ale, a beer brewed without hops, and beer, a beer produced exclusively with hops.
     Hops had an advantage over other bittering herbs in that it also had preservative qualities.  A beer that used hops as the bittering herb would stay fresh longer than an un-hopped beer.  This was a vitally important point in the commercialization of beer.  Beer that stayed fresh longer meant that brewers could expand the area to which they could export beer.  And because hops were not a church monopoly they could produce beer for less and undersell their competition.  The church, of course, did not take this lying down, nor did the brewers of ales.  In some areas the cultivation of hops, the importation of beer, or even the brewing of beer were forbidden.  Eventually, however, beer emerged triumphant.
     The Celts, later the Cymri, were in contact with two cultures about which we know a little of their brewing ingredients.  In recent past the Scandinavians have used Juniper and Sweet Gale to flavor beers.  The Anglo-Saxons also used Sweet Gale as well as Honey and Yarrow.  In 1577 an English author by the name of Gerard mentions that the brewers in Cheshire and Wales put Ground Ivy in their "beers".  Given that hopped beer was common in England at this time, Ground Ivy might have been a holdover from the pre-hops days, or it might have been a folk medicine of some sort.  The Welsh also produced a beverage known as 'braggot' which was a combination of honey and ale.  I have seen many versions of braggot recipes which run the gamut from hops-flavored-mead to honey-flavored-beer and everything in between.  One recipe listed no less than eight herbs and spices to be added to the mix in quanitities about six times larger than brewers would add to a regular mead.
 Early brewing techniques were fairly simple.  The grain was harvested and the chaff separated out.  The grain was then wet, by various techniques, and laid out to sprout.  Once the grain had sprouted it was roasted in an oven and then boiled in water with any flavorings.  This mash was left to ferment for a few hours to a few days and then strained.  The ale or beer could then be drunk.  The left over solids that were strained out could be added to the next mash, thus ensuring that successful strains of yeast were introduced, or could be used in bread making, fed to the livestock, or mixed with more water to produce a weaker beverage generally referred to as 'small-ale'.  The ale had to be drunk within the next several days, if it was not then it would go bad and was only fit to feed to the pigs; possibly giving rise to the expression "Drunken swine".
     Small beer or, in this case, small ale would be made by boiling some water and letting it cool to body temperature.  This would be added to the solids removed by the first straining and allowed to sit for a day or so.  This would then be strained and the solids used for baking or fed to the livestock.  The resultant beverage would be a slightly alcoholic drink for consumption at meals and by small children.
     So what might a Cymric Celt of around 500 AD have ordered at the bar?  Well, the grain components are problematic.  Oats, rye, barley, and wheat all grow in Wales and all have been used at one time or another for brewing.  But of these four barley has always been the preferred grain.  So let's assume that barley is the grain used.  The process of malting was well established by this point, so the barley was probably sprouted and then roasted in an oven.  Flavorings are another problematic point.  Our list includes Juniper, Sweet Gale, Honey, Yarrow, and Ground Ivy.  Juniper is more of a Scandinavian plant and Honey was probably too costly in Wales for anything other than mead or braggot,  so that leaves us with Sweet Gale, Yarrow, and Ground Ivy.  All are possible, but I'm going to pick Ground Ivy because it is a weed and grows everywhere.  In all likelihood the brewers would have used a gruit that contained more than one herb, but let's keep it simple.  The leaves and/or flowers of Ground Ivy were probably added to the mash after boiling and then removed during the first filtration.  The length of the brewing process is another uncertainty.  While some Anglo-Saxons can be documented as having brewed their beer in under a week and consumed it even more quickly, the Norse began preparing their beer several weeks prior to a feast and then, presumably, consumed it all during the feast.  Let's go with a compromise and say that the beer ferments for four to seven days, depending on the ambient temperature (colder = longer, warmer = shorter) and how long the barm (the scum of foam on top) lasts.  It is then strained through a coarse sieve and left to sit for several hours to a whole day.  It is strained again, this time through a fine sieve, and is now ready to drink.  Later in period the brewer might dump the brew into a barrel, seal it, and let it sit for a while (how long, I don't know).  Continued fermentation would produce a slight carbonation that would quickly dissipate after the barrel was broached.
     So what would it taste like?  There's no way to tell for sure until someone makes it (sounds like a Pennsic project to me).  But let's take a guess.  According to Mrs. M. Grieve, author of A Modern Herbal, Ground Ivy has a balsamic odor and a bitter taste.  So the beer would smell different, be warm, silty, and have no carbonation.  Your guess is as good as mine as regards the taste.  Such a 'green' ale would probably have some nasty side effects, such as increased flatulence and digestive discomfort.  The alcohol content would be about equal to or a little less than modern beers.
     A final point, everywhere I have used the word 'he' you can substitute 'she'.  Records indicate that from Babylonia to Egypt to Scotland brewing was the almost exclusive province of women up until the 19th Century.  Of course, once it became a profitable commercial venture, rather than just housework or maintaining a small alehouse, men stepped up to seize control.

If you're interested:

  The Regia Anglorum folks conducted an experiment in brewing back in '92 and it's documented at their web site at:
                    http://www.ftech.net/~regia/brewing.htm

  There is a web page devoted to Alcohol in the Middle Ages.  The section on beer is located at:
                    http://www.geocities.com/Paris/1265/cbeer.html

  The SCA newsgroup had an intelligent discussion on brewing back in '93 and it is archived at:
                     http://www.pbm.com/~lindahl/rialto//beer-msg.html  A really good resource, believe it or not.