This thought originally came from a Dan Carlin episode about the Sea People. If I remember correctly one group's name was written "PLST." Some people today think it could have been pronounced Peloset, like an early version of Phillistine.
Who the PLST were doesn't really matter to this question though. How did the people who spoke these languages know what vowel sounds to make? Was it implied by the consonants? Like a P followed by an L always had a soft e sound between them?
Languages do not omit vowels. Orthographies may emit them. Don't confuse writing systems for languages.
As for how people would know what to read a word as if the vowels were't written, a lot of it has to do with context. Many modern languages do not write the vowels, even if they can be written. Arabic and Hebrew are examples of such languages.
For a native speaker this doesn't matter, since you learn to speak the language before you learn to read the languages. You know what the word is that's been written down because you already know the words it could possibly be, and the context tells you exactly which one that is. Words don't exist in language without context.
There's been a lot of talk in linguistics over the past decades about the idea of ambiguity avoidance, how languages much have something going on to keep things from being ambiguous. However the consensus now is that this doesn't really exist, and it doesn't need to, because the thing that prevents ambiguity is the context.
There's another part to your question which you don't ask directly but which your question hints at, and that's the notion that there is one period-independent way to pronounce the name. This is not the case. The pronunciation would likely change over time from generation to generation. The idea of having a standard spelling is historically new, and until fairly recently, spellings of words were not fixed. Even after spelling systems did become more standardised, they still change over a period of generations in order to better reflect the newly developed pronunciations as words.
To add to all that, the early alphabets did not have vowels to begin with. The Phoenician alphabet, one of the earliest, had none at all, and the letter <饜> that eventually became <A> was actually the consonant /蕯/. Vowels only came later on in the history of writing.
tl;dr: Native speakers would know how to say a word before they'd learn how to read a word, context would inform them of which of the possible candidates it should be, and anyway the pronunciation would change over time so it's not like there was always one correct pronunciation throughout history to begin with.
/r/linguistics is a better spot for this.
FYI, Hebrew is a modern (and ancient) language where native speakers don't need vowles to read it, so that may be a good place to start.
I can answer regarding Hebrew, but not regarding other languages. In Hebrew, the main letters are just the consonants, and the vowels consist of small dots and accents around these consonants. It can get annoying to write the vowels, particularly because a native speaker doesn't need them in order to understand the word. So, they're often omitted because putting them in is pointless effort.
As an example, consider the sentence "I love my dog."
It's easier to write without the vowels, and anyone who can read Hebrew still knows what it says.
A point that the other responses haven't addressed is the use of determinatives.
Determinatives function as a kind of clue to what the consonants might say. They are not voiced, but just act as a guide to what kind of word is meant. Imagine if we didn't use the vowels in English and you were confronted with the letters TRN. This could mean 'turn', 'train', 'torn' etc. But say at the end (or start) of TRN there was a symbol of a line looping around and an arrow at the end pointing backwards. You would realise it meant 'turn'. This is how determinatives work.
In languages like ancient Egyptian, which is what you're referencing here, there are no vowels, so they used a system of determinatives to show what kind of word was meant. In the case of Palestine or 'prst' (it's written with an 'r' not an 'l' in Egyptian), it can be found with a 'hill' determinative, which means foreign country, or the 'people' determinative, as seen here as the three lines and the human figure just to the left of the crack.
Often context is enough, but many ancient languages used determinatives to add clues for the reader.
.JPG){kind=link}