The French scientific higher-education system is weird and misunderstood even in other European countries, so here's a (very simplified) explanation of the road I followed and how much it cost.
After high school, if you have good enough grades (say top 10%) you can enter something called Classes Préparatoires, which is a rather intense scientific (Math + Physics) preparation for competitive exams for the Grandes Écoles. It lasts two years, three if you decide to repeat the second year because you are not satisfied with your results at the exams (repeating the first year is forbidden, if your fail you have to go to a regular University - which is also cheap anyway -, but only 10-20% fail the 1st year).
There is a lot to say about how the way we are taught in Classes Préparatoires should change, but there is something right about them: they are completely free. Oh, and if you (your family) cannot afford rent and/or food, you can get funding from the government for this.
After Classes Préparatoires, if you succeed at the competitive exams, you get into a "Grande École" (Engineering School). Studies usually last three or four years and you get a Diplôme d'Ingénieur at the end (basically what you call MSc in the US).
All the top Grandes Écoles are public and depend on different ministries (Education, Industry or Defense). The cost of studying there is below €1000/year. You can still be subsidized if needed, and you are encouraged (actually it is even mandatory) to make paid internships which pay for your studies. Actually, the two top Engineering Schools (Polytechnique and École Nationale Supérieure) even pay students who study there.
Oh, and you are encouraged to go abroad. You can do an internship in another country or go there to specialize during your 3rd year. In my case I went to a British University to specialize in Distributed Computing. The cost of studying there is much higher but since I was a guest student from another European University I didn't pay (except campus rent). It also works with the US, although I am not sure how: some friends did the same thing at Standford and MIT.
In the end, I got two MSc-s (one in France and one in UK), and my tuition fees for the entire thing amount to about €3000.
There are very few things I think a State should pay for, but top higher education is definitely one of them.