A single heating pad draws 750mA when powered from a 5V source (according to the web site you linked to). That's within the capabilities of the MOSFET you are using, but only just. The datasheet FQP30N06 datasheet doesn't tell us much about what happens with \$V_{GS}=5V\$, which in itself is a strong hint that this device is not really suited for such low gate drive signals. There is only one graph I can find that tells us anything useful at \$V_{GS}=5V\$, on page 3:

This tells us that at 750mA drain current (lower than the graph even shows), you can expect less than 0.1V between drain and source. This will keep power dissipated in the MOSFET well under 0.1W, so the MOSFET might get warm, but not as hot as you describe. Even at 0.5W of power, the transistor shouldn't get hot enough to melt plastic.
That being said, even with just a single heating pad, you are working right on the edge of the MOSFET's capabilities, and I would recommend a MOSFET with significantly lower \$V_{GS(TH)}\$, much less than the 4V for this device.
With two pads, the current that should flow, if they really do have 5V across them, is \$2\times 750mA=1.5A\$, which you obviously are not achieving (you quoted a current of 1A max), and which means that the actual voltage across those pads is more like:
$$ V = IR = 1A \times \frac{6.5\Omega}{2} = 3.3V $$
This is probably due to the batteries and/or regulator being unable to maintain 9V and/or 5V under such a load. To test this theory, you should verify that the 5V source is actually staying at 5V when the two heaters are simultaneously powered, without the MOSFET; that is, connect those pads in parallel directly between the regulator's 5V output and ground, and see what happens to battery voltage and regulator output.
This brings me to a much bigger problem. Even if the regulator and batteries are able to tolerate a 1.5A load (two pads), the regulator will be dissipating a lot of power. It will drop 4V across it (the drop necessary to go from 9V to 5V), while passing 1.5A. That's a power dissipation of:
$$P = IV = 1.5A \times 4V = 6W $$
The regulator would be heating almost as much as the heating pads, enough to destroy it in short order, if it didn't protect itself by dropping out. The fact that it doesn't blow up is telling me that the batteries or the regulator (or both) are dropping out, which is preventing the regulator from dissipating such a large amount of power. Again, check your 5V regulator output, and battery voltage, to find out if I'm right.
Now, if the regulator output drops below 5V, and the Arduino can still operate, it's obvious that the gate drive signals to the MOSFET will also be lower than 5V, and you have a situation where the MOSFET can never be fully on, which will cause it to start heating up, too! The increased on-resistance of the MOSFET will reduce heating pad current, which will reduce demand from the batteries and regulator, and the whole system will find some equilibrium in which everything is getting hot.
You can't use a single FQP30N06 MOSFET to operate both heating pads. The right MOSFET could do that, but not the FQP30N06. You can, however, use one FQP30N06 per heating pad, I believe that's within this device's capabilities. The resulting circuit might look like this:

simulate this circuit – Schematic created using CircuitLab
Firstly, notice that I reduced gate resistance R1 a lot, from 10kΩ down 470Ω. This keeps gate charging current to within the capabilities of the Arduino output (10mA or so), while causing those gates to rise and fall in potential as quickly as possible. That way, the MOSFETs spend as little time as possible in a not-quite-on, not-quite-off state, wasting battery energy and heating up.
This doesn't solve the problem of regulator over-heating, which is by far the greatest problem you have with your design. The only solution I can think of is to power the heating pads directly from 9V, instead of requiring the regulator to do all the heavy lifting.
You might say that the pads are designed to operate from 5V, but that's just SparkFun talking. It's more appropriate to say that the pads are designed to operate at \$P=I^2R = (0.75A)^2 \times 6.5\Omega = 3.6W\$.
It doesn't matter what voltage (within reason; 9V is fine) you apply across the pads, as long as on average you have 0.75A through them, for an average power dissipation of 3.6W.
Consider the following design:

simulate this circuit
I've connected the top ends of the heater pads directly to +9V insteads of +5V, bypassing the regulator altogether. Now the regulator is providing only a few milliamps to operate the Arduino and other low-current-demand systems.
Of course, this means you cannot switch the heater pads permanently on, because with 9V across them, they will pass \$\frac{9V}{6.5\Omega}=1.39A\$ and will dissipate \$ P=\frac{V^2}{R}= \frac{9^2}{6.5} = 12.5W\$ each. What you can do, however, is switch the MOSFETs on and off rapidly, using one of the Arduino's PWM outputs (at a low PWM frequency, perhaps 1kHz, for example).
By setting the PWM duty cycle to \$\frac{3.6W}{12.5W}=29\%\$, you set the average power to the prescribed 3.6W.
Beware, though, rapid switching of current demand from the 9V supply will create significant voltage dips of that supply at the PWM frequency, some of which will make it past the regulator. You must mitigate this with C1 (electrolytic) and C2 (ceramic), to decouple this switching noise from the rest of the system.
Also, don't forget the usual 10nF or 100nF (ceramic) supply decoupling capacitor, one for each and every IC, very near to the IC's positive/ground pins. The Arduino already has them, but there's no harm in adding another 100nF right across its power input.
Update
User @Rmano commented with a brilliant twist, which seems obvious in hindsight, but which I'm sad to say I didn't think of myself: wire the two pads in series, and power them directly from 9V.
The power dissipated by the pair in total would be:
$$ P = \frac{V^2}{2R} = \frac{9^2}{2 \times 6.5} = 6.2W $$
They would both share the 9V equally between them, for 4.5V and 3.1W each, a little short of the specified 3.6W, but close enough.
The current through both would be less than the 750mA through a single pad powered from 5V:
$$ I = \frac{V}{2R} = \frac{9}{2 \times 6.5} = 690mA $$
That means you can use a single FQP30N06 MOSFET to switch them both simultaneously, from a regular non-PWM on/off control signal. The idea could be implemented like this:

simulate this circuit
There is one potential gotcha here, that @Rmano alluded to, which is that this setup could fail if the pads' temperature coefficient of resistance is positive. That could lead to thermal runaway, as one pad heats up more than the other; its resistance increases faster, causing its voltage to increase while the other pad's voltage decreases, which further exacerbates the disparity, and so on, until one of the pads overheats.
It's easy to test for. Just connect the two pads in series, directly across 9V, and keep an eye on voltage across either one. If, after some time, either voltage exceeds 5V or drops below 4V, then you can't employ this series arrangement, at least not without some additional mitigating scheme.