Why do sidebands appear after Amplitude Modulation?
AM means that the amplitude of the carrier is multiplied by the payload signal plus some offset.

The multiplication theorem for sine says

\$\sin(a) \cdot \sin(b) = \frac{1}{2} ( \cos(a-b) - \cos(a+b))\$

Let \$a=2\pi f_c t\$ be the carrier phase and \$b=2\pi f_s t\$ the phase of a sinusoidal payload signal then as a result of AM (=multiplication of sines) you get a sum of two sinusoids. The frequency of one of them is a little bit below (\$f_c-f_s\$) and one of them a little bit above (\$f_c+f_s\$) the carrier frequency.

This works not only for a payload signal that is a pure sine wave but also for a whole band (any signal can be seen as a sum of sinusoids).
So as a result you get one band above and one (mirrored) below the carrier frequency. 

(Note: The offset mentioned in the beginning results in the fact that also the unchanged carrier frequency will be present after AM; but I've neglected that for simplicity).

BTW: 


  we never tried to mess with the frequency of the carrier


AM does mess with the frequency. 
It's a missconception that multiplication of two signals wouldn't mean messing with the frequency; that's true only for multiplication by a constant; that's a linear operation; multiplcation of two time varying signals is not. Any non-linear operation introduces new frequencies.
Simple example: frequency doubling (=messing with frequency) of a sinusoid can be done by simply squaring the signal (=multiplying by itself).