Having recently spent some time in France, one of the first things I did was attempt to acquire a 3G data SIM for my phone. Having a local sim makes it really easy to get around using various smartphone apps (eg maps, train timetables and general internet goodness).
After a fair bit of research, I realised that there are no official mobile carrier outlets in the airport. So there is no easy option. Buy you can get a limited access sim from a newsagent..
I got to Charles de Gaulle airport in Paris, and discovered that the SIMs can be purchased at the "Relay" newsagent stores there. I got mine from the outlet in the car rental hall. There is also an outlet near the arrivals gate at 2D, though I don't know if they also have SIM cards.
Ask for an "Orange mobicarte SIM". It will cost EUR9.90 (as at July 1, 2012). Also buy a EUR10 recharge (you will get a paper voucher with a 14 digit code on it).
My Samsung Galaxy 3 takes micro-sims (same as iPhone). But the store only sold regular sim cards. If you have a micro-sim phone, you'll have to buy the regular one and make sure you have packed a small pair of scissors or pocket knife. With some delicate trimming of the soft plastic, you can trim it down to size, using your existing sim as a template.
The SIM card will come with about EUR5 credit, and should work immediately when you stick it in your phone. My Android required no configuration, it just worked.
HOWEVER this data access will run out in under a day due to the default expensive data plan, and you'll need to charge it up in order to enable the unlimited data plan (which costs EUR9). This is the tricky bit..
In order to add credit, you need to "activate" the card, which involves presenting photo i.d. and having your details entered into the Orange system. The shop I bought the SIM from did not do this (more accurately, they either cannot do this, or they forgot to offer to do it). Perhaps the shop will do this if you ask, or at the post office also in the car rental hall. But you must get it activated.
I did neither, and had to find an Orange outlet store in the town I was staying, where they happily took my passport and French address details, then activated the card, all for no charge. At the outlet they told me specifically that Internet Max is only available on contract, not prepaid. Not true in my experience, it still worked, so don't tell them about this or listen to their claim. Maybe it will change soon?
The card activation can take up to 48 hours, in theory. I had to wait overnight for it to work (call 224 ; if you get intro music, it's activated. If you get scolded in French without music, it's not activated). Once activated, you can add the credit you bought and enable the unlimited internet plan.
Instructions for enabling internet are here:
They are largely correct, except that the Internet Max option is not under "Multimedia" any more, but "internet et e-mails". Also, it activated pretty quickly for me, within about 15 minutes.
After all this, things just work. 3G/HSPA/etc are pretty broad across the country, though there are a lot of areas where you'll find only Edge. It was rare to get zero data access (even in rural areas).