The signal should be amplified with a low noise 'instrumentation' amplifier to get it's full range signal up the match the range of the ADC, say 5V. Otherwise you are wasting ADC resolution. Someone else can answer the analogue, though I believe that has been answered on electronics.stackexchange already.
My reading of that sensor data sheet is the senor is very slooooooooooow compared to digital technology. It says it's response time for 'T90' < 5 seconds, and 'T99.5 < 40 seconds.
If you could explain exactly what those terms mean, I might be able to be more exact in my answer, but I'll give you the punchline anyway, because it appears to help.
There are purely software techniques for increasing the resolution of an ADC which work by taking multiple samples.
This is not simply taking multiple samples to do normal averaging to reduce error.
Instead, the technique extracts more information about the signal from many samples.
The technique is called "Oversampling and Decimation"
It can be made to work in a couple of ways, and this Atmel application note "AVR121: Enhancing ADC resolution by oversampling" explains how. It has a worked example, which looks very similar to your scenario.
A Mental model
It might be easier to think of the real sample having a tiny (less than 1-bit high) saw-tooth signal added. The saw-tooth must not be synchronised with sampling.
Draw a voltage vs time graph, volts up, time right.
Draw a steady, horizontal, real signal.
Then draw horizontal lines to represent the measured digital value. The signal will be somewhere between two lines.
Then draw a saw-tooth signal, 1 bit high, sitting on top of the horizontal real signal
When the steady signal is close to the next higher digital value, the saw-tooth crosses up above that value 1 higher.
When the steady signal is barely above its measured digital value, the saw-tooth hardly ever crosses up above that value 1 higher.
(I will try to find time to draw this, I can't find the picture by searching)
The maths:
When a real signal 'r' is measured it is rounded down to the nearest digital value by the ADC. Let's call that rounding down floor(), and let's say how many bits the ADC measures.
So, a signal r is measured by a 10-bit ADC as a number, call it 's', = floor(r, 10)
Let's call the amplitude of the saw-tooth at any instant t, we don't know what it is, except it is less than the voltage between any ADC value, and the next. For a 10-bit ADC measuring 0-5V, the maximum value of t is 5V/1023, or roughly 5mV.
Now let's think about a long stream of values from the ADC. Remember, it is measuring r with the saw-tooth voltage t added.
Then each time the ADC samples, the answer is the real signal r and the saw-tooth.
s = floor(r+t, 10)
The saw-tooth will sometimes push s 1 bit higher than r alone would be measured because the saw-tooth happens to be big enough when added.
If the signal r is almost at the digital value r+1, then a lot of the samples with t added in will be measured as s = r+1. If the real-signal r is barely above r, then almost all will be at s = r
This is key:
when r is very close to s+1 (but just under it), t pushes lots of ADC conversions high enough to measure as s+1
when r is far below s+1 (very close to s), t pushes very few ADC conversions high enough to measure as s+1, so most are still measured as s
So, if we add up a long sequence of ADC values, s, the ratio of s=r values to s=r+1 will give us more information. The ratio of s=r to s=r+1 tells us the value of r in that 1-bit, 5mV voltage range. The saw-tooth (not synchronised with sampling the signal) extracts that information.
The nice part is we don't need to count the ratio of s to s+1. We just add the sample values, and shift right (to get the correct number of bits). The number of +1's is added in, and that is the right ratio.
Now here is the sneaky part.
Random (Gaussian) noise acts in a very similar way to the saw-tooth signal. It gets added anyway, for free. We don't need to do anything except add a sequence of values. The only downside is noise takes more samples than a saw-tooth. In this case, I don't think it matters.
Summary: add enough samples then the low-res ADC acts like a higher resolution ADC.
How effective is this?
That document has a table, but let's pick a few, using a 10 bit ADC (e.g. an ATmega328P)
11 bits - 4X samples
12 bits - 16X samples
13 bits - 64X samples
14 bits - 256X samples
By adding 256 samples, a ATmega328P's 10bit ADC provides 14 bits of resolution.
An ordinary Arduino, samples at roughly 9.6kHz, and that sensor looks so slooooow, it shouldn't have changed much while sampling.
TI's application note "Oversampling Techniques using the TMS320C24x Family", AKA spra461.pdf has some useful diagrams and explanation of superimposing a triangle wave, which increases resolution with fewer over-samples that noise.
Side note: If you are confident with programming, consider getting an ST Micro Nuceleo. They are mbed's, so the software is instantly available from mbed's cloud. ST's Nucleo's cost about 8GBP. They have one or more 12bit ADC's built in. Most have 1M samples/second ADC's, and the STM32F302 and STM32F334 have 5M sample/second ADCs. The extra 2 bits mean they only need sample and add 16 values. So they could provide 14bit resolution at a higher sample rate than the raw ATmega328 could provide 10 bits. This isn't an advert for ST. Any MCU with a faster higher-resolution ADC will perform in a similar way.
Punchline
That sensor specification seems to be so slow, that by using this purely software technique, the 10bit ADC on the ATmega328P will provide 14bit resolution. In fact, it could provide 15bit resolution by adding more samples.
