I've heard that aircraft cycles depend on the number of missions, regardless of the distance, because the pressurisation of the aircraft at altitude is what causes cumulative damage to the fuselage. If that's the case then does it tend to be true that aircraft that fly lower have more cycles? I'm particularly wondering about the difference between turboprop (FL240) and jet aircraft (FL410). Do turboprop fuselages tend to have more cycles?
It's a lot more than just pressurization cycles (all sorts of things are being flexed), but yes. Turboprops are somewhere around 1 hour per cycle and regional jets about 1.2 or 1.3 hours per cycle (a typical regional jet will do around 3000 flying hours and about 2400 cycles in a year). Mainline jets are closer to 2+ hours per cycle, with long haul jets around 3-4 hours per cycle.
So a turboprop with 50000 hours will tend to have 50000 cycles (averaged across the fleet), the RJ with 50000 hours will have around 40000 cycles, while a 777 with 50000 hours might only have 20000 cycles (keeping in mind wide variations from aircraft to aircraft).
So yes the short haul commuter and regional equipment does get flogged like mules compared to their luxuriating mainline big brothers. Whether this becomes a "premature" problem depends on how robust the original design was. The beefier the metal with a given load profile, the more times you can flex it before it starts to crack. But when you make it beefier, you are adding "ballast" from the perspective of the short term mission. So it's a trade off between performance now, and viability when the airframe gets old (the extra beef reduces payload upfront, but adds greatly to the residual value of the airframe 20 years later - some operators will prefer one approach, some the other).
When the first high-time DeHavilland Dash 8 got to 80000 cycles, the original structural life expectancy, they only found a couple of minor cracks. This eventually led to an extension of the structural life limit to 120,000 cycles, giving a huge boost to the market value of old Dash 8s. Airlines that own their Dash 8 cared greatly about this. Airlines that leased their airplanes knowing they'll turn them in at a certain point long before, not so much.
CRJs on the other hand, are bit less robust and a CRJ200 needs quite a bit of patching of the structure after 40000 cycles to keep it viable to its 80000 cycle airframe life (a consequence of not doing a full fatigue test program at the very beginning - they only tested a fuselage barrel, with the full program being done about 8 years later). You can keep flying it past 40000 cycles without the reinforcements, but the frequency of the repetitive inspection requirements imposed make that uneconomical.
On the other hand, the cost of all the patches was brutal, and a lot of CRJ200s were simply retired at 40k, and their airframes stripped for spares, because the operators didn't want to spend the money to incorporate all the structural Service Bulletins (Embraers like the 145 are even lighter in their construction and considered even more "disposable" - a 145 once had its back broken, became an instant tail dragger, on a hard-ish landing in Brazil, a landing that wasn't hard enough to blow tires).
None of this really impacts safety if the maintenance program was developed properly, because inspection intervals and procedures prevent structural issues from progressing to a dangerous level, plus damage-tolerant structural design and very large (3:1) scatter factors applied to fatigue test results (if you bend a component repetitively in a fatigue rig, and it starts to crack at 60000 cycles, you have to impose an inspection or repair or life limit of some kind at 20000 cycles).
Notwithstanding "outlier" events like Aloha Airlines. Things always get through the cracks.
Aircraft fatigue life is generally defined in terms of cycles and flight hours. Cycles better reflect the damage created by shock loads, as occurs in taxiing (braking/turning on ground), takeoff (high power/vibration, load transfer from landing gear to wings) and landing (impact, braking). However, the aircraft is still under cyclic loads caused by engine vibration and turbulance in cruise and that also consumes fatigue life. For this reason, aircraft have cycle and flight hour limits for overhauls (where components are checked for microcracks) and total life limits where the component or the entire aircraft is scrapped.
Turboprops have relatively higher cycle life wrt a jet airliner, but this is not related to cruise altitude or any particular trait of turboprops. Instead, the aircraft is designed to reach its cycle and flight hour limits simultaneously, so that the aircraft can serve for as long as possible. Turboprops have higher cycle limits because their flight legs are shorter relative to jets.