Yeah...no. So here is how this myth was read back into the sources by modern readers making connections that the medieval authors definitely did not make themselves.

There is Carolingian-era text called the Capitulare de Villis that sets out, in haphazard order, a list of provisions or rules or guidelines or ideas for how to run the royal estates (which are scattered throughout the empire). You can read a translation of the text online from the University of Leicester. It's very, ahm, early medieval in approach, with provisions like:

-- Those who have vines shall keep not less than three or four crowns of grapes.

-- That every steward, on each of our estates, shall always have swans, peacocks, pheasants, ducks, pigeons, partridges and turtle doves, for the sake of ornament.

-- It is our wish that whatever we or the queen may order any steward, or whatever our officials, the seneschal or the butler, may order them in our name or in the name of the queen, they shall carry out in full as they are instructed. And whoever falls short in this through negligence, let him abstain from drinking from the moment he is told to do so until he comes into our presence or the presence of the queen and seeks forgiveness from us.

You will notice that I did not quote a passage involve flax or linseed or linen, and in fact, if you Cntl/Cmd+F through the linked page, you will find those words to be very much not appearing outside the context of linen as fabric.

Provision 70 includes a laundry list of plants that stewards ought to grow on their estates. The specificiation of types of apple is a nice touch, but relevant here is the list of herbs:

It is our wish that they shall have in their gardens all kinds of plants: lily, roses, fenugreek, costmary, sage, rue, southernwood, cucumbers, pumpkins, gourds, kidney-bean, cumin, rosemary, caraway, chick-pea, squill, gladiolus, tarragon, anise, colocynth, chicory, ammi, sesili, lettuces, spider's foot, rocket salad, garden cress, burdock, penny-royal, hemlock, parsley, celery, lovage, juniper, dill, sweet fennel, endive, dittany, white mustard, summer savory, water mint, garden mint, wild mint, tansy, catnip, centaury, garden poppy, beets, hazelwort, marshmallows, mallows, carrots, parsnip, orach, spinach, kohlrabi, cabbages, onions, chives, leeks, radishes, shallots, cibols, garlic, madder, teazles, broad beans, peas, coriander, chervil, capers, clary. And the gardener shall have house-leeks growing on his house.

(I had never heard the term "rocket salad" before, which is apparently arugula, and that is just AWESOME. Words are cool.)

There is STILL not flaxseed or linseed mentioned anywhere here.

Enter the medieval inheritance of intellectual antiquity.

Charlemagne's court hosted the heart of a little-r renaissance of learning. Established scholars from elsewhere in Europe were invited, and came. So you had a concentrated group of people with overlapping but differing intellectual backgrounds--basically, a whole lot of knowledge coming together in one place.

It has been noted that the list of herbs here bears similarity to lists in Pliny the Elder, whose work in various remixes was quite well known among medieval scholars. One of Pliny's sources is the History of Plants by Theophrastus. Theophrastus mentions the uses of several herbs for the benefit of oral health. Relevant here--FINALLY RELEVANT HERE--is that flaxseed is useful in little potpourri mixes to treat toothaches.

At this point, it's almost beside the point to say scholars aren't quite sure how to deal with the Capitulare de villis. Most scholars would probably say it represents an ideal to live up to rather than being a list of provisions that were followed to the letter. There is an overall tendency in the text for the points to revolve around the production of sufficient goods to supply the king/his immediate surrounding, and then to ensure the actually supplying happens, which points to the general ethos of the time.

But none, absolutely none, of this is to say that Carolingian peasants were offered the choice of flax or death.

--

Edited for clarity per /u/ParallelPain's request