When do I know it's best to replace it?
After it smoked, it's necessary to replace it. See the "Absolute Maximum Ratings", first page of the datasheet. You've clearly exceeded that maximum temperature.
Physically, failure modes of overheated semiconductor devices involved migration of dopants, degradation of insulation, degradation of thermal coupling, … So, things you don't easily see. An IRL540N is between 1 and 2€ in single quantities – so definitely not worth risking it.
How do I prevent the smoking? It's getting too hot.
It would seem that way, yes! So, you need to stop it from getting so hot.
What's a good heat sink for such applications? I'm surprised it got so hot as it's winter and the ambient temperature is close to 12-13°C.
You didn't install it on a heatsink to begin with? I'm a bit surprised: The Junction-to-Ambient thermal resistance from the datasheet says 62 °C/W, so, with a loss of only 3 W, you'd be far into "beyond repair" territory.
Anyways, I'm not sure why you have that loss. The currents you're switching are low, and at your (starting) temperature and this current, the on-resistance should be far below 1 Ω. In fact, looking at Fig 1. from the datasheet, at 7A your Drain-Source voltage would be < 0.3V for any reasonable Gate voltage, so you'd be converting 0.3 V · 7 A = 2.1 W into heat. Sure enough, that's a lot, but according to the datasheet thermal resistance should heat up your case to little more than 120°C hotter than ambient – not smoking hot.
So, three things are possible: you're using a gate control voltage that's too low, the current is higher than you say, or you're swithing the MOSFET on and off a lot – but these are motors, so I'm pretty sure you wouldn't want to PWM them?
In any case, when you have something that produces ~ 2W of heat, yeah, a heatsink is desirable – but a cheap one should do. All heatsinks will come with some specified thermal resistance. That, added to the thermal resistance from the MOSFET datasheet from junction to cooling surface, will tell you how hot the chip gets when you generate some defined heat power.