With patience
They would have to know in advance that the process would take at least a generation.
As people grow older it becomes harder for them to learn a new language and be proficient in it. So it's better to teach the kids, and to do that you need to give them the tools, and the motivation.
tools: this is the easy part. The education system's whole purpose is to pass on knowledge that fits the government's whims, so use it to teach them the new language.
motivation: of course, you want the kids to speak the language fluently, not just enough to get a good grade. So they need a reason to want to learn, or for their parents to push them to learn. Examples include:
- all university studies are in the new language
- all government services are in the new language
- entertainment like TV, movies etc are in the new language
Real life examples:
As mentioned, when Israel was founded the Hebrew language didn't even exist as it is today, and now it's the official language. Many immigrants don't speak it very well (almost all the population are immigrants or 2-3 generation in the country) but their children all do.
The Italian language was also introduced in an attempt to unite all the various cultures under one language, which obviously was a success
Another example from Israel: when you speak to people (mostly girls) at the ages 25-30 they have a really good knowledge of Spanish. The sole reason being a series of Spanish soap operas that were the best thing to watch for kids in the 90s.
What about illiterates?
You mentioned that the population is mostly illiterate. The thing about this is, if you don't have education it's really hard to pass on knowledge. Some system needs to be in place in order to teach kids the language.
If your determined to teach the language and keep the population illiterate, my best suggestion is an army of nannies that speak the language and provide free (perhaps even mandatory) child-care. There's no better way to learn than to have someone speak to you when you're a kid. Then, you also need to keep some motivation for the kids to keep practicing the new language, as mentioned above. The fact that every kids speaks a language that none of the parent do might act in your favor actually.