The most common way to solve this is to use an op-amp to scale up the voltage swing of whatever sensor it is you're using, so that it maxes out at 5V. The op-amp is an all-round amplifier/converter chip for this kind of thing. See this
page, which specificially talks about scaling sensors that put out less than 5V.
The other option is to use the AREF pin to tell the ADC what the maximum reference voltage is. There's not much documentation on this, but see Massimo's post half way down this page
. He makes the very good point that at .5V full range, your resolution will be .5 millivolts, and noise will be a big issue! You would also need a very very very clean and stable .5V reference supply... many headaches indeed.
Hope this helps