What to look for in the datasheet when choosing a MOSFET?
The 12V and 6A is a good starting point. This tells me you need a mosfet with a max drain-source voltage capability greater than 12V so 20V would be a minimum criteria for this.

You want to switch 6A and you'll want it to do so with minimum volt-drop - just like a relay contact so you are looking for Rds(on) below (say) 0.1 ohms. This means at 6A it will develop a small voltage across the device of 0.6V (ohms law).

However, that will produce a power disippation of 6 x 6 x 0.1 W = 3.6W so if you are looking for a surface mount device you would prefer a lower disippation of maybe 0.5W max.

This means Rds(on) would be more like 0.014 ohms.

So far, your application needs a 20V transistor, capable of switching 6A with an on resistance no more than 0.014 ohms.

Vgs is "like" the coil voltage on a relay - it's how much voltage you need to apply to the coil to get it to switch BUT for a FET it's a linear thing and, if you don't apply enough voltage, the mosfet will not turn on properly - its on-resistance will be too high, it'll get warm under load and have a volt or two across it when you want a nice low resistance. 

You then need to inspect the details of the spec to see how much you need to apply to guarantee the low on-resistance you want. A bit more on this further down.

The IRFZ44N has on the front page of the data sheet: -

Vdss = 55V, Rds(on) = 17.5 milli ohms and Id = 49A

It's not a surface mount device therefore a little more heat generated isn't going to matter too much (with a heatsink) so it'll do what you want it to do but I'd research a device with smaller Vds (say 20V) and you'll probably find one with a lot less than 10 milli ohms on resistance.

If you look at the electrical characteristics on page 2 you'll see that the 17.5 milli ohms on resistance requires a 10V drive voltage on the gate (3rd line down in the table). Less than this drive level and the on-resistance rises as would the heat produced.

At this point I can't decide for you any more but I think you might be looking for a device that will operate from logic levels. In which case the IRFZ44N won't do.

The STB36NF06L is a little higher with the on-resistance but the spec does suggest it will work from a 5V drive on the gate - see electrical characteristics (ON) but i'd still be tempted to find one that is more suitable.

I'd be tempted by this. The PH2520U is a 20V, 100A, 2.7 milli ohm device when the gate voltage is 4.5V. If your logic levels are 3V3 check figure 9 to see it will work well at 3V3.

One last thought about things - you are wanting to PWM a load and if the frequency is high you'll find that the gate capacitance takes some drive current into the gate to get it moving up and down quickly. Sometimes it better to trade off on-resistance to find a device with lower Vgs capacitance. You're into horse-trading now. Keep as low as you can on switching frequency and it should drive ok from a 5V logic pin.