From the German side of things:
- Whenever you become unemployed, you can probably be covered in one way or another. If you get unemployment benefits (ALG I), the Bundesagentur für Arbeit pays a predefined amount of money to your previous health insurer, who should continue to cover you. If you don't get unemployment benefits because there is a Sperrzeit (i.e. you quitted a job without a serious reason), the Bundesagentur für Arbeit will nonetheless cover health insurance costs. There are also some situations in which your current insurer has to cover you for one month at no costs to ensure a seamless transition.
- At the end of your unemployment benefits, you fall under the ALG II system and there is some mechanism to get free health insurance as well (free to the beneficiary that is, the insurer – Krankenkasse – still receives money and the federal budget covers the costs).
- If you are privately insured, things are more complex. You might lose the right to stay in your current contract/be forced to switch to the statutory health insurance system. When privately insured, you don't have a European Health Insurance Card (EHIC) either so you are not necessarily covered in France.
- All this (ALG I, ALG II) requires being a resident and “available” for a new job, which also means being able to show up if the Bundesagentur für Arbeit wants to see you.
- Moving to your spouse or registered partner is a valid reason to quit your job. Moving to your girlfriend/boyfriend isn't but you can still get a (partial) exemption from the Sperrzeit on a case-by-case basis. Do apply for that if necessary.
From the French side of things:
- If you live together with someone who is covered by one of the French statutory health insurance schemes, you can also be covered yourself at no extra cost (unless you get a job in which case you must insure yourself independently and pay the mandatory contributions). It's easier if you are married or in a registered partnership but it's still possible if you are merely cohabiting. This would be the most obvious solution in your situation, at least if one of you is working in France.
- In principle someone who is inactive needs health insurance to have the right to reside in France but if you look for work, you are a “worker” as far as EU law is concerned. As an EU citizen looking for work, the general case is that you should be covered by your previous country of residence, using an EHIC.
- Do note that statutory coverage in France (“part sécurité sociale”) is not complete, there are not-insignificant copayments for many things (GP visits, medicines, a “room and board” fee when you are hospitalized, etc.). Many French people have additional private insurance to cover this (a “complémentaire santé” but people typically call this a “mutuelle”) but with the EHIC you only get basic coverage (also in my experience the CPAM people are very nice to deal with and make no difficulties in recognizing a claim based on the EHIC… but require a French bank account to actually transfer the money).
- In some cases, it might be possible to register to the French “couverture maladie universelle” (CMU) but only after three months in the country. The difficulty is that non-active people cannot generally get it, employees are supposed to be covered by a regular health insurance scheme, families are automatically covered if one member is covered and unemployed people from other EU countries should have an EHIC. So to get the CMU, you must show that you are really looking for work (to avoid being classified as inactive), that you have no other way to be covered and ask the authorities to make an exception. Theoretically possible but expect a lot of paperwork (in French!).
- Another option is to try to get a job quickly, any job really. Working has two advantages, it gives you the right to reside in France (not a big issue in practice for EU citizens but still, see On what grounds can an EU country deny entry to other EU citizens? and this question on the politics Q&E site for details) and it “opens up rights” (ouvrir des droits in French) to health insurance immediately and for a long time. For example, if you work at least 60 hours in a month, you have health insurance for two years after that (i.e. even if you stop working, you remain insured). Waiting tables for two weeks would be enough for that.
To make the transition:
- I am not sure about all the details but you have the right, under EU law, to go to another EU country to look for work. It should even be possible to transfer your rights to unemployment benefits (ALG I) to another country using something called the “U2 document”. Even if you don't expect large benefits or don't plan to rely on them, it would have the advantage of allowing you to remain in the German “system” completely legally while being abroad.
- Unfortunately, it might be necessary to deal with all the paperwork before moving to France. If you want to do everything by the book, you need to register with the Bundesagentur für Arbeit, make sure they processed your application and nothing is missing, get the U2 document, maybe apply for a waiver of the Sperrzeit or the requirement to look for work locally before moving abroad and make sure your health insurance still covers you. Start before your last day at work.
In any case, note that beyond the risk that something bad happens while you are not covered, a gap in health insurance is not such a big issue in most European countries. In Germany or France, whenever you get a job, you have to get insured and the statutory health insurers have to cover you under the same conditions as everybody else. Private insurers in Germany can require a health check and/or adjust payments whenever you enter a new contract but for statutory health insurance it really makes no difference whether you had uninterrupted coverage or not.
