Is Adafruit's recommendation for led strip driver MOSFET incorrect?
If you examine your picture it is for a drain current of 31 amps: -



And clearly, if you look at figure 1 in the DS you will never get gate-source voltages of 3 volts or 3.5 volts able to produce a drain current of 31 amps.




  So when driving the transistor with 3.3V voltage, wouldn't it heat too
  much? Is it a mistake in their article or maybe I'm missing something?


With a 3 volts gate source voltage and a more moderate drain current of (say) 1 amp the DS volt drop will be typically 0.1 volts and the power dissipated will be 0.3 watts. Use the 2nd picture for detailed analysis of power dissipation with different gate-source voltages.