Magman is best fought with the fire sword (Fire + Cutter), which can be obtained during the fight or at the very end of 4-4. The fastest strat in the previous level involves entering the Magman fight with just cutter. The Magoo enemies that spawn before Magman attacks give fire, so it can be combined in the following way:

One out of ten times, none of the three Magoos spawns next to where Kirby is standing. Instead of risking a long throw, I keep the cutter powerup and deal two hits to Magman, and then try combining again in the next cycle.

There are three possible attacks in the first phase. There is a slow pattern where three columns of lava come out (left video), and two hits are possible. The "curly arm" pattern (middle) is vulnerable for long enough to get three hits. The third pattern, where four columns come out one by one, is the nicest because you can get four hits off. In terms of which patterns are possible, the third pattern never shows up as the first cycle, and no pattern is repeated twice in a row.

The second phase also has three different types of attacks, but Magman can be finished off before he starts a second attack. After each of these attacks, finish Magman off by throwing the double powerup for two hits of damage.

In one attack, Magman can spawn a bunch of rocks (left). These rocks are randomly positioned, but usually you can headbutt them out of the way without getting hurt.

Magman can also breathe fire (middle). It's possible to get three hits in before he starts the attack. While he's breathing the fire out, you can hide right underneath, and for some reason, throwing the sword next to him actually connects with his hitbox.

In the third attack (right), Magman will dive, leaving him invulnerable for about seven seconds. It's possible to do risky strats with the Burnis enemies, but I don't think it's worth it.