If you are a foreigner interested in applying for a job in France, how does it work? Here is my understanding. (The rules change a little bit over time, so my knowledge might be not quite up to date.)
The jobs: in computer science, there are two types of research-only positions: CNRS and INRIA, called "charge de recherches" at the junior level and "directeur de recherches" at the senior level. Academic positions that combine research and teaching are called "maitre de conferences" at the junior level and "professeur" at the senior level, and usually require the applicant to speak French or show the ability to become fluent in French within a year or two so as to be able to teach in French. All of those positions are typically tenured.
Most foreign applicants are primarily interested in CNRS or INRIA positions, so I will focus on those. Pros: no mandatory teaching; no stress about job termination, since the job comes with tenure; living in France. Cons: low salary; living in France. INRIA tends to do research that is somewhat more applied than CNRS, so I will focus on CNRS.
CNRS typically gives funding for researchers to do their work in university labs, so that one is a "CNRS researcher working at University x", in the same way that in the US you can find an "NSF postdoc working at University x". It is possible for a CNRS researcher to change labs and move his job with him, giving the position great flexibility.
It is a national process, with a centralized selection of all CNRS researchers for the entire country. Researchers in theoretical computer science normally belong to "section 6" (unless they fit in one of the cross-disciplinary sections or in the somewhat more applied section number 7) and the selection will be done by the CNRS committee for that section. At what level should someone apply? The guideline is: if the starting date is less than 4 years after the PhD, one is expected to apply for a "CR2" (second class researcher) position, although exceptions can be argued (note that the French PhD is usually awarded after 8 years of higher education). For 4 years or a few more beyond PhD, the norm would be "CR1" (first class researcher). Someone at the tenured level would apply at the "DR2" level (second class research director). A mid-career researcher and beyond would apply at the "DR1" level (first class researcher), if such a position exists that year. It is possible to apply at several levels simultaneously. There are three things that the applicant must do, listed below.
1. Informal contacts. At the present stage - beginning of November - interested applicants must as soon as possible make contact with the places that they might wish to join. In France, departments are structured into research groups, and realistically there is no point in applying without the support of the research group that one wishes to join. A group realistically can support at most one applicant. Now is the time to work these things out. The CNRS applicant can list up to 3 departments that he or she would be willing to join, and gives an order of preference between the three.
2. Written application. The website to apply to CNRS opens on Dec 3, 2012. The deadline for applications to be in will be about a month later: last year it was on January 5 at 4pm. Regardless of what's written on the official application web page, an applicant must make sure to communicate to CNRS, in addition to the required forms, all the information that normally goes with a job application, for example, recommendation letters. After all applications are in, CNRS does a preliminary filter, then selects some applicants for an interview.
3. Interview. The interview will be short (half an hour, maybe) and include a presentation by the applicant and questions from members of the CNRS committee. In the presentation, the application will impress upon the committee how great he or she is. In the questions, those members of the CNRS committee who support other candidates, hence are against that applicant, will try to expose the candidate's weaknesses, so the questions are often on the tough side. CNRS does not pay for travel expenses for the interview.
Outcome. After the interview, the applicant's work is done and all they can do is keep their fingers crossed. The CNRS committee then chooses who to recruit, using some complicated combination of how strong their application looks, how compelling their research area, whether it's a high priority (for that, it's better to work in an area that is under-represented in France), whether or how they will fit in their research environment in France (for that, it is better to work in an area that is well represented in France). CNRS then assigns each successful applicant to one of the departments he or she listed, taking into account the applicant's ordering of the departments they listed, the quality of the fit, and the perception by the committee of national priorities (for example, CNRS often tries to fight centralization by preferring new hires to do research in labs outside Paris).
Unofficial news come through the grapevine right after the committee meeting, confirmed by the next level up a couple of months later (with occasional surprises: it is not unusual that the list of successful applications is changed a little bit), and eventually officially assigned by a formal letter that arrives much later, towards the end of summer, so that the successful applicant often moves to France, finds housing and gets settled before getting the official letter.