We applied Ensemble Empirical Mode Decomposition (EEMD) for the first time to ionosonde data to study trends in the critical frequency of the F2 peak, foF2, and its height, hmF2, from 1959 to 2005. EEMD decomposes a time series into several quasi-cyclical components, called Intrinsic Mode Functions (IMFs), and a residual, which can be interpreted as a long-term trend. In contrast to the more commonly used linear regression-based trend analysis, EEMD makes no assumptions on the functional form of the trend and no separate correction for the influence of solar activity variations is needed. We also adopted a more rigorous significance testing procedure with less restrictive underlying assumptions than the F-test, which is normally used as part of a linear regression-based trend analysis. EEMD analysis shows that trends in hmF2 and foF2 between 1959 and 2005 are mostly highly linear, but the F-test tends to overestimate the significance of trends in hmF2 and foF2 in 30% and 25% of cases, respectively. EEMD-based trends are consistently more negative than linear regression-based trends, by 30-35% for hmF2 and about 50% for foF2. This may be due to the different treatment of the influence of a long-term decrease in solar activity from 1959 to 2005. We estimate the effect of this decrease in solar activity with two different data-based methods as well as using numerical model simulations. While these estimates vary, all three methods demonstrate a larger relative influence of the Sun on trends in foF2 than on trends in hmF2.