How is music encoded in a vinyl? I'm asking about something that looks like magic to me. I know that waves can be combined into one by "summing" them, but I guess there are different combinations of waves that lead to the same resulting wave. I also know that the movement of the needle througout the vinyl  is what holds the information that aftwerwads makes the sound. 
But how can all those sounds be enconded in a 2-dimensional movement (maybe 3-dimensional if the needle goes up and down?) without any loss of necessary information? I've heard that is has to do with Fourier Analysis, which I'm not an expert of, but it's okay if you relate to that in you answers.
Also, do our brains intervene in this recreation of the sound in a way that is not necessary to encode all the information, but just enough to let our brains to the rest (for example something similar occurs with harmonic sounds)?
 A: TL;DR: No information is lost because you only need 1 dimension of motion to reproduce a sound wave.
The field of audio engineering and recording is decades old, and there is a mountain of research on how best to record and play back sound. The process I describe here is most likely not reflective of the state of the art, and necessarily skips over many details; this answer is meant to illuminate the conceptual underpinnings of the recording process at its simplest level.
The motion of a needle in a record player is indeed 2-dimensional. We can decompose this motion into 2 components: the (pretty much constant) forward motion of the needle around the record, and the (highly variable) side-to-side motion of the needle as it's deflected by the sides of the groove that it's in. As long as your record player is good enough that the forward motion is basically constant, we can basically ignore the forward motion and treat the needle as an object that moves in only 1 dimension, side to side within its groove.*
The needle is connected to a diaphragm, which is basically just a thin, flexible membrane. When the needle moves side-to-side, it moves the diaphragm in and out (in other words, the 1-D motion of the needle is coupled to the 1-D motion of the diaphragm). When the diaphragm moves in and out, it pushes and pulls on the air, which creates pressure waves; these pressure waves are, in fact, what sound waves are. These sound waves travel through the air and into someone's ear, which has another diaphragm in it (your eardrum). The pressure waves move this diaphragm in and out, which deforms some hairs that are touching it. The particular way in which the hairs are deformed generates an electrical signal, which travels to your brain; your brain takes this electrical signal and interprets it into the perception of sound. So basically, the playback of a record is just one diaphragm vibrating another diaphragm, which are linked by a column of air.
Recording works basically the same way as playback, but in reverse. Sounds (pressure waves in the air) push a diaphragm in and out. This diaphragm is connected to a needle, in such a way that the in-and-out motion of the diaphragm causes a side-to-side motion of the needle. The needle is traveling through the groove of a blank, soft record (usually made of lacquer). Before the needle passes, the grooves have straight walls. As the needle passes, the side-to-side motion of the needle deforms the soft walls of the groove, which remain deformed, preserving a record of the needle's side-to-side motion. For playback, this soft record is then turned into the normal vinyl one, so instead of creating new deformations, the needle will be deflected by the ones that are there.
The fact that the recording and playback processes are (in the limit of a perfect process) exactly the reverse of each other means that in the ideal case, the deformations in the walls of the groove in the record cause the diaphragm to vibrate in exactly the same way that it did when recording. As such, no information is lost, in the ideal case. In reality, neither the recording nor the playback process is perfect, so very low-frequency sounds (which only very gently move the needle) and very high-frequency sounds (which move the needle faster than the soft walls can react) are not likely to be accurately recorded or played back. This manifests itself as an absence of bass and a high-pitched hiss when playing back most vinyl records. In addition, dust contamination and manufacturing defects will cause pops and crackles in the playback, and warping of the record or inconsistency in rotation will cause a slow "wobble" in the sound. But on paper, this process does not have any inherent information loss.
*The needle's side-to-side motion and its forward motion are actually coupled; the faster the needle moves forward, the more rapidly it will encounter deformations in the sides of the groove. As such, variations in forward motion will cause variations in the overall pitch of the sound, which we usually call "wobble".
