Magnetic and inertial measurement units (MIMUs) proved to be an accurate alternative for optic, electromagnetic, or acoustic measurement technologies. While the orientation of the MIMU could be estimated using accelerometer, gyroscope, or magnetometer sensors alone, many studies proposed sensor fusion algorithms (SFAs) to overcome the drawbacks that appear when each sensor is used individually. However, the performance of such SFAs highly depends on their gains, and poor initialization or incorrect adjustment of the gains would degrade the SFAs’ performance. Therefore, this article proposes a general framework to find the optimal adaptive gain tuning scheme for Kalman filters and complementary filters to achieve accurate and robust orientation estimation with MIMUs. To this end, we proposed an innovative optimization framework to find the fixed optimal gain of an SFA or the optimal adaptive gain regulation scheme. Also, we demonstrated that the designed adaptive gain regulation scheme (a hard switch with two or three levels or a fuzzy inference system) is essential for orientation tracking with various SFAs. We measured the thigh, shank, and foot motion of nine participants while performing various activities using MIMUs and a camera motion-capture system to calculate the MIMUs’ error in 3-D angle estimations. Gain regulation by hard switch was significantly ( $p ) more accurate and robust than it was for innovation adaptive estimation. Also, for all tested SFAs, hard switching for shank and foot MIMUs was significantly more accurate or robust than that for fixed optimal gain. Our experimental results showed that the adaptive gain tuning of SFAs using optimized gains is crucial, regardless of the algorithm structure or complexity.