The word "palate" comes from Latin, and its metonymic use as "taste" was already present in Roman antiquity. We find it e.g. in Cicero's De Natura Deorum II.18:

Quæ, si bis bina quot essent, didicisset Epicurus, certe non diceret. Sed dum palato, quid sit optimum, judicat, cæli palatum, (ut ait Ennius) non suspexit.

Had but Epicurus learnt that twice two are four he certainly would not talk like that; but while making his palate the test of the chief good, he forgets to lift up his eyes to what Ennius calls “the palate of the sky.” (Rackham translation)

Was this linguistic image based on their actual beliefs about the world? Yes; we find it explicit in Quintilian, Institutio Oratoria VI 3.19:

When, therefore, we speak of the salt of wit, we refer to wit about which there is nothing insipid, wit, that is to say, which serves as a simple seasoning of language, a condiment which is silently appreciated by our judgment, as food is appreciated by the palate [quod sentitur latente iudicio velut palato], with the result that it stimulates our taste and saves a speech from becoming tedious.

Was this belief widespread? Let's consult Pliny's Naturalis Historia, the Wikipedia of the age:

With all the other species the tip of the tongue is the seat of taste, but in humans this is also situated in the palate (intellectus saporum ceteris in prima lingua, homini et in palato). (XI 65, Loeb translation)

So it's not that the palate was believed to be the seat of taste; it just was one of the seats, along with the tongue. And Pliny was entirely justified in this claim (at least the part about humans); for we do actually have taste buds in the soft palate—as well as the upper esophagus, inner cheek, and the epiglottis.

(Unrelated aside: I cannot resist quoting my favorite term for "epiglottis" from Holland's delighful translation of Pliny: “Under it, there is a little tongue (which the Greekes call Epiglossis) at the root of the other: and the same is not to be found in any creature that laieth egs.” How I wish we used transparent wording like "little tongue" for this kind of thing…)

---

Did they get this notion from the Greeks, who informed so much of the Roman worldview? In Greek the palate was just the "sky" (ouranós) of the mouth, as in many modern languages. In Plato, Theaetetus 185c, we find this:

Socrates: […] if it were possible to investigate the question whether the two, sound and color, are bitter or not, you know that you will be able to tell by what faculty you will investigate it, and that is clearly neither hearing nor sight, but something else.

Theaetetus: Of course it is,—the faculty exerted through the tongue. [glôssa]

No mention of the mouth-sky, then. In Aristotle's On the Soul there's a long discussion of how taste is generated when the tongue touches liquids, or liquefying matter; the tongue is identified as a special kind of flesh that can taste, and distinguished from all other flesh, with no special mention of the palate. A look through a couple Ancient Greek dictionaries found no sign of the roof-sky being used as a metonymy for "taste" (if anyone know of examples please post them!).