The most important specs for our application are (in no particular order) drain to source voltage (when the device is off), drain current (when the device is on), Vgs threshold, and Rds on.
Vdss just needs to handle your battery configuration (2 in series would be 8.4V max, 2 in parallel 4.2V max). Almost anything you find should handle this.
Id should handle a little more than your max drain from the battery... I don't think you can find batteries that can source much more than 30A, but if you wire in parallel that would be 60A.
Rds on is also important. You want to minimize the power dissipation in the FET. So get the lowest Rds on that you can. There are devices with single digit milliohm Rds (and some that are hundreds of microohms).
Vgs threshold is a measure of how much voltage you need to across the gate and source to activate the FET (close the circuit). Since we only have the battery voltage to apply here, better make sure this value isn't too high. There are plenty of devices with logic level gates (3.3V, 5V, etc...). Of course most devices have the Rds on and the current handling specified with 10V Vgs. So you may have to look at the datasheets to see how it will perform with worst case battery voltage (I generally find I like to recharge my single cell mechs when the battery is around 3.7V resting).
Now, I don't know if you were planning a series or parallel build here... A fairly nice part that is currently $0.81 at digi-key is Alpha&Omega AOI510. Rds on looks to be 6 milliohms or under for Vgs 3.5V and greater. At that state it can handle 35A (max power dissipation in the device is 7.5W without heatsinking). It's really challenging to find something that will have a low Rds with the low Vgs that we can provide. And if you can provide some heatsinking the thing can easily handle 50-70A. With a series build your Vgs would be more like 7V minimum and Rds on would be more like 2.7 milliohms, so you could handle 50-70A with no heatsinking.