Briefly put and somewhat simplified (someone please correct me if I'm missing something), the threshold voltage is the gate voltage at which a MOSFET begins to turn on.
More voltage is needed to turn the FET 'more fully on' (graphs of 'transfer function' in a datasheet should illustrate that).
Threshold voltage varies with temperature, and for a given device, will also vary significantly between one device and another - datasheets might specify some combination of typical, minimum and maximum threshold voltages, but they aren't consistent in which of those figures they quote.
Therefore if you want the FET to be adequately turned on with a ~3-3.5V gate voltage, I'd be tempted to choose a FET where the maximum gate voltage was specified in the datasheet, and that maximum was low.
Also, you do want a fairly low 'on' resistance if you're looking at a 10A load, to avoid wasting voltage and heating up the device.
Given how many MOSFETS there are around, recommending a particular one is tricky - I don't know how 'popular' particular devices are, and therefore how likely they are to be stocked by particular distributor.
If I was buying from my supplier (Farnell):
I'd start by narrowing my search to N-channel devices in TO-220 packages (if I was happy with a device that size)
Then select devices with a threshold voltage below ~1.5V (that's likely to be a 'typical' figure for the device, not a maximum).
Then I'd probably order by threshold voltage and work through the list looking at low resistance devices, looking at the linked datasheets to see how various devices compared.
Bear in mind that the 'on' resistance is often quoted for a higher gate voltage - at lower gate voltages the resistance will be higher and so you will want to allow for that.
For example,
http://www.irf.com/product-info/datasheets/data/irl3303pbf.pdf
came up as a possible device, but the datasheet only gives a minimum threshold voltage (1V) and looking at the graphs for a [presumably 'typical'] device, something like 3.5V at the gate would be needed for a 10A load.
Similar devices from the same manufacturer also only specify a minimum threshold voltage, so I'd tend to ignore them as well.
However,
http://www.st.com/web/en/resource/technical/document/datasheet/CD00001901.pdf
looked possibly rather better. (typically capable of 25A load at 2.5V gate voltage)
Just to double-check, I upped my threshold voltage limit to 2V, and ordered the results list to show devices where the 'on' resistance was specified at 5V rather than the more common 10V, since that was likely to show devices tailored for low gate voltages.
Doing that, I found:
http://www.nxp.com/documents/data_sheet/BUK954R4-80E.pdf
Which I had initially excluded since the threshold voltage was higher (1.7V), but that was the typical voltage rather than the minimum, and the range was tighter - the maximum figure wasn't much higher (2.1V), and was rather lower than the maximum for the previous device.
Typical max current at 2.5V gate voltage seemed slightly better as well.
Of the three, I'd probably go for the last one, or some similar related device.
I'd probably buy a device or two to play with and measure what the voltage drop across a particular one was at full load and a nearly-empty lithium cell - given how much devices can vary, there could be meaningful differences between one and another.
However, those variations can also make recommendations based on experience tricky - someone could come along and say '
Just use an XYZ1234 - it works fine' and then you buy one and it doesn't work for you, just because they were luckier than you.