What sort of wattage should the 12v LED strip power supply have 24,36,60...?
It depends on the power rating for the LED strip(s). If they don't give you a power rating they should give you current rating. Power is calculated as Voltage x Current.
Give yourself some safety margin... Don't push the power supply to it's limits.
What power supply should I get if instead I decided to use the Single 1W or 3W LED?
High power LEDs (1W or more) require a special [u]constant-current[/u] power supply. That would be separate from the Arduino's "normal" (constant-voltage) power supply.*
Will any of these power supplies will be able to also provide current to the Arduino Mega?
The regular 12V supply can power the Arduino and LED strips (as long as the power supply can supply the power/current). 12V [u]commercial/architectural LED bulbs[/u] have the constant-current power supply built-in, so they can also run from a regular 12V power supply if you find one that runs on DC. (Most of these are designed as plug-in replacements for incandescent bulbs that run from a 12VAC transformer.)
- Regular little LEDs require constant (or "controlled current") too, but the current is limited with a resistor. Most LED strips use a resistor on each LED. But since the resistor often dissipates more power (as heat) than is consumed by the LED, a resistor as a current-limiter isn't efficient with high-power LEDs and of course you heed a high-power resistor. Resistors in LED strips are not efficient either, but at least the heat is spread-out.