|MadSci Network: Engineering|
The answer depends on what you mean by "exactly the same way." The fatigue on the aircraft depends on the forces on the structure and the number of times those forces are experienced. You're talking about fatigue caused by similar maneuvers, so let's just assume that the only way we would see more fatigue on a structure is by seeing larger forces.
You're definitely right that the density difference at different altitudes will cause an aircraft to behave differently, but if you have the fighter perform a turn at a given g-level (this would be equivalent to having it hold a certain turning radius if its speed remains constant), then that defines the forces that will be seen by the structure. In other words, a 5 g turn at 5000 ft. will involve the same forces as a 5 g turn at 25000 ft. The only difference will be that the aircraft must maintain a higher angle of attack (or higher speed) at the higher altitude because the density of the air is lower.
However, if the fighter were to hold the same angle of attack during the maneuver, or use the same control inputs at different altitudes, different things are going to happen. You might even have a situation where the same control inputs would cause a climbing, 5 g turn at 5000 feet, but a descending, 2 g turn at 25000 feet. In this case obviously the 5 g turn will have higher forces associated with it, so you'd expect to see more fatigue on the structure. However since fighters are designed for high g maneuvers, you wouldn't expect to see much difference in the performance of the structure unless you repeated this experiment many many times.
I hope this helps.
Try the links in the MadSci Library for more information on Engineering.