Help designing an inverse polarity and overload (crowbar) protection circuit
So for polarity reversal causing no damage and requiring no fuse replacement you can use pretty much whatever diode you want and put it in series so that "normal" current flow passes through the diode only if properly plugged in.  With the current requirements and voltages that you're working at, this shouldn't be an issue. A simple silicon diode should be fine.

For overvoltage you're going to want a circuit more like what Nick Alexeev suggested in the comment.  Essentially a zener diode with a PTC or other type of fuse.  The Zener should have a value which is less than the maximum input to your regulator. 

So basically, if you reverse batt_in+ and batt_in- the first series diode will prevent any current from flowing and protect your circuit.  If batt_in is greater than the breakdown voltage of the zener, it will start pulling down a lot of current, and blow the PTC fuse.

The only extra thing you might do, is to guarantee that the startup current doesn't exceed your PTC's current limit, you can place a resistor on "protected V_IN+" or "protected V_IN-" (in series before the regulator and decoupling capacitor) such that:

(BATT_IN+ - V_forward_diode - Resistor*Maximum_expected_load) >= Vmin_regulator

For the desirability of any specific characteristics for the PTC, the diodes, and everything else, it all depends on your application.  In general, I tend to wing it unless I have a real reason to crunch the numbers.  I'm also a bit too tired (on my way to bed) to really get into how to calculate what these values should be, but if you need this info ask in a comment and I'll post some tips on getting the numbers.

Though, why not just use a polarized connector for the batteries so that you don't have to worry about whether the connector is plugged in backwards?  And in what context are you going to overvolt?  Think about these questions too when trying to answer a more complicated design choice (a polarized connector is easier than adding an extra diode, and is less likely to lead to extra design considerations).

Hope that helps!