MOSFET Over Heating. So hot it's melting the solder
It sounds like you need a heatsink.

Another thing to check is your gate voltage when you have the FET switched on. If your Gate-Drain voltage is too high, the MOSFET may not be properly biased on, a situation which would generate a lot of heat.

Also, how often is this switching? Is it a steady-state thing, or is this part of a switching supply? If it's a switching supply,  you will also need to look at the rate at which the system switches.



Anyways, assuming you have everything biased properly (probably a safe assumption, but measure it anyways):

RDS(on) = 130mΩ @ G-D voltage of 5V  

So, with 130 mΩ in series with 3A:

$$V = 0.130 * 3$$
$$V = 0.39$$
$$Power = V * A$$
$$Power = 0.39 * 3$$
$$Power = 1.17W$$

So you're going to be dissipating 1.17W of power in the MOSFET, in the best-case situation.
That will get very toasty without a heatsink. If you're just running this as a bare TO-220 device, it getting extremely hot isn't too suprising.



So, assuming we have a TO-220 in free-air:


  TO-220 junction-to-air thermal to ambient equals 62.5 degree per watt.   


(From here)

Therefore:

$$Δ°C = 62.5 * 1.17$$

$$Δ°C = 73.125$$
$$Device Temperature °C = 73.125 + Ambient$$
$$Device Temperature °C = 98.125$$

So assuming ideal thermal dissipation on a bare TO-220, it's still going to easily reach ~100°C.
Any environmental factors that further reduce the device's cooling will make it worse.