Google defines "linear" as "arranged in or extending along a straight or nearly straight line." Wikipedia tells me that "linearity refers to a function or relationship which can be graphically represented as a straight line". Such systems can be described by an equation of the form $y=mx+b$.
In the case of RF amplifiers, the relationship is the input voltage vs. the output voltage. The output is identical to the input, only "louder". Mathematically, $V_{out} = A \cdot V_{in} + 0$, where $A$ is the voltage gain of the amplifier.1
Linearity is a generally desirable property but it comes at the cost of reduced efficiency. At any instant, the amplifier's output is probably something somewhere between its power supply rails, and consequently, the output transistors will have some voltage $E$ across them and some current $I$ through them. The rate of electrical energy consumption is the product of these two: $P=IE$. That consumed energy can't vanish: it's converted into heat. This requires big heatsinks, and it drains your batteries faster or runs up your electric bill.2
Here's a solution to the heat problem: we amplify the input signal so much that the output is always greater than the supply rails. Now we are effectively connecting the load directly to one supply rail or the other. Now the output transistors either have 0V across it,3 or are passing no current. Thus, the power ($P=IE$) in the transistors is low because always either current or voltage is nearly 0. The energy is going to the antenna, not to heating the transistors.
The problem is now that the output is horribly distorted. If the input was a nice clean sine wave, the output will be a square wave, full of odd harmonics. We can remove4 the harmonics with a filter, and because the filter is made of reactive components like inductors and capacitors which alternately store and release electrical energy, rather than converting it to heat, they don't get so hot, and the amplifier is more efficient.
This mostly solves the distortion problem, but something is lost: the amplitude of the input signal. Fortunately, the frequency is preserved.
So now we know when non-linear amplifiers are acceptable: when the amplitude of the signal is insignificant, such as FM, or frequency modulated digital modulations like FSK, some PSK flavors, or GMSK. Modes where amplitude is significant like AM, SSB, or digital modulations like QAM require a linear amplifier.
1: RF amps tend not be to be marketed by their voltage gain, but by their maximum power output. Assuming a 50 ohm load, power is related to voltage by $P=E^2/50\Omega$. Take the output power and the input power, calculate the associated voltages, and the ratio of the two is the voltage gain of the amp.
2: To dive more deeply into the reasons linear electronic circuits make waste heat, check out My linear voltage regulator is overheating very fast on electronics.SE. Though that's about voltage regulators, the problem is common to a broad class of linear electronic circuits. You can also read about power amplifier classes. Class AB is a common linear RF amplifier design. Class C is common for non-linear amps.
3: Real transistors will always have some small voltage across them, even when fully on, which means they will get a little warm. This is far better than the a lot warm they get in a linear amplifier, however.
4: really, just attenuate. Significantly and sufficiently. All amplifiers output harmonic distortion of some degree, and regulatory agencies regulate the maximum allowable harmonic distortion.