The ADC cannot operate with a reference voltage below about 1V, BTW - the built-in analog reference is 1.1V, but that's still not going to help you much.
You need to amplify the signal. This is a classic case of needing an instrumentation amplifier since your signal is so small. Look at the specs for the MAX4208 for example for a 5V single-rail device with rail-to-rail capability.
http://www.maxim-ic.com/datasheet/index.mvp/id/4925 - other manufacturers make instrumentation opamps too!
Alternatively a single-op-amp circuit can be used but won't be as accurate due to time and temperature drift. Depends on your precision requirements (you'll definitely need a 'precision low voltage' opamp that works down to the negative rail. If your sensor has a high output impedance the instrumentation amp is the best route I think.