Will these heatsinks be sufficient for the mosfets

Don't be shy about spec'ing your own part from a distributor's website. It's not as hard as you'd think, once you learn which parameters are important in which situations. Based on the information you've provided, I'll guide you through selecting a usable MOSFET on Digikey.

Note that I am not validating your schematic design in any way, since you didn't provide one. One thing that stood out to me in your description was the LED supply voltage (6V) and the FET's gate voltage (5V). Make sure you fully understand how to interface a P-Channel MOSFET before you make this circuit. You will have to do more than just connect an Arduino pin directly to the gate.

Anyway, on to Digikey:
1. Search for "MOSFET" and click on the "In Stock" checkbox.
2. Choose "FETs - Single" under Discrete Semiconductor Products.
3. We want to whittle-down the 16,000+ options as much as possible, but without limiting ourselves. First, select the two "P-Channel" options under the FET Type filter, since we want a P-Channel FET.
4. Select all of the "Logic Level Gate" variations under the FET Feature filter.
5. Digi-Reel, Tape & Box, and Tape & Reel are codenames for "minimum order is, like, a million". So select everything in the Packaging filter except those three.
6. You said the power supply is 6V, so you shouldn't need to filter under the Drain to Source Voltage (Vdss).

There should be a large amount of FETs left. At this point I'd sort by price and start looking at what the least expensive components are like. The main parameter that's left is current. Forget about what Digikey is reporting under "Current - Continuous Drain". Those numbers are usually unrealistic values advertised by the manufacturer. You shouldn't expect to push that much current through the FET unless you've specifically designed it for that purpose (i.e., thermal considerations).

Instead, let's approach it another way by picking a FET based on its Rds(on). Let's assume something in a small package will have a thermal resistance of about 100 degrees C/W. That means for every Watt of power, it will increase 100 degrees C. Actually, 100 degrees rise in temperature is probably a good design point. That leaves a little bit of room before the typical maximum silicon temperature of 150C. So we want to pick a FET that will dissipate no more than 1W at the 1A you specified: $$P=I^{2}R$$ Rearranging and solving for R: $$R=\frac{P}{I^{2}}=\frac{1W}{1^{2}A}=1\Omega$$ Now we can start from the top of the price-sorted list and look for FETs that have 1\$\Omega\$ or less Rds(on). At this point, any one you choose will do fine. Just read the datasheet first to avoid surprises later!

By no means is this a comprehensive method for choosing a FET for all circumstances. But for the simple application you're doing, this method is good enough.

If I use the procedure I wrote at the beginning the temperature rise becomes

ΔT = P × θ = 30 × 62 = 1861°C

But this is insane. ... Do I need a heat-sink here?

You are neglecting to consider the heat capacity of the chip. This acts like a capacitor in the thermal equivalent circuit, connected between Tj and (some arbitrarily defined) ground, which prevents the chip from heating up instantaneously. Unfortunately you are unlikely to find good data on exactly what the value of this capacitor should be.

You can refer to the safe operating area curve for your MOSFET:

Based on this it's probably safest to keep your switching time below 10 ms, instead of close to 1 s as you have currently.