When used for low-frequency switching (almost DC operation, or tens of Hz), just pick an overly huge FET to eliminate losses almost completely and be done with it.
As stated before, you really need to work backwards from your thermal point (and possibly, acceptable efficiency, i.e., voltage drop to the load) to find maxium acceptable Rds(on), but sometimes the current rating is easier to find in the datasheet for the first-order device selection; in that case, the rule of thumb I use, is:
Absolutely necessary derating is: double the current rating, i.e., 10A part for 5A load.
For extremely low frequency switching (< 10Hz): preferably use at least 5x the current rating, i.e., a 25A part. Even 10x derating makes a lot of sense.
(This rule only works if you use the gate voltage that the FET really needs for proper switching, i.e., the curve that doesn't "level off").
The nice thing about FETs is that they have no bottom limit for decreasing conduction losses; you'll get asymptotically nearer to 100% efficiency and no losses at all. So if you have the money to buy a large $1 FET instead of a cheap $0.20 part, just do it. You can get away with no thermal design whatsoever, and still get something ridiculously fancy like a 5 degC temperature rise.
For fast switching, it's not so easy; the larger FETs will require stronger drivers. Driving them from just a microcontroller pin will cause much MORE losses (compared to a small fet) every time it switches, and that will become the killer in kilohertz range.
Another thing about FET selection is the maximum voltage it can switch, i.e., maximum Vds. As a rule of thumb, you need double the voltage that you'll switch. It's not that datasheets usually lie, but due to real-world effects like wire inductance, you'll have voltage spikes much higher than your actual voltage, and you can verify it with high-speed oscilloscope. Anyway, the thing is, the higher the maximum Vds rating, the harder it will be to find FETs that switch properly with low gate voltages! If you only have 3.3V, you are pretty limited to 20V or maybe 25V FETs, which will limit the switched voltage to 12V and even then you really need to do it right. With 5V, you could go up to 30-40 volts in FET rating.
OTOH, slow switching helps with voltage spikes, so the MCU pin driving the gate may actually be a good thing. But add a series resistor approximately matching the MCU pin equivalent resistance to prevent ringing. Something like 47 ohm will stop ringing without slowing down it too much.
If your load is a mechanical valve (a coil), it will require a freewheeling diode in parallel. But it probably already has it, given that your FET hasn't blown already.
Also, as a general rule, datasheets include those minimum/typical/maximum values; in addition, they often provide separate data for different temperatures. Always find the worst case for your calculation, sometimes it's the "minimum", sometimes the "maximum". For example, FETs increase their Rds(on) at higher temperatures, and at the same time, allowed heat dissipation is lower. Both of these work against you at the same time.