I only have a vague idea of what characteristic impedance
Characteristic impedance is the ratio of voltage to current (thus, an impedance) for signals propagating along the trace, which is determined by the balance of capacitance and inductance along the trace.
It should be dependent on the length and the frequency, how come it isn't?
Characteristic impedance depends on the ratio of inductance to capacitance. Since both inductance and capacitance increase linearly when the trace length increases, their ratio doesn't depend on the trace length.
Also, within limits, these parameters also don't change much with frequency, so again the ratio doesn't depend on frequency and the characteristic impedance doesn't depend on frequency.
Intuitively I should calculate the characteristic impedance of each pad-to-pad trace and make sure it is always 50Ohm. Is that the case?
If the driving circuits are designed to drive 50 ohm loads, then generally yes. You also want to provide matched termination at at least one end of the trace, and possibly both, depending on the details of your circuit.
Generally you don't have to make a separate calculation for each connection. You just look at your board stack-up and find a trace width that achieves 50-ohm characteristic impedance, and make all of your traces that width. You might use microstrip, stripline, or coplanar waveguide geometry depending on the circumstances of your layout. You would do a separate calculation for each signal layer on your PCB, and maybe for the different types of geometry (microstrip and coplanar, single-ended and differential) if you need to use all those combinations.
If the trace length is less than about 1/10 of a wavelength at your operating frequency, then you can often get away with using an unmatched trace.
typically, multi-layer boards consist of single-sided or double sided PCBs glued together. So that glue/lacquer fills these voids – the typical few µm aren't a problem to fill.
Now, I haven't thought about that, but obviously, a board manufacturer would choose a glue/lacquer that has comparable dielectric properties as your substrate. For FR4, that might be quite possible; whether that works with more exotic materials such as ceramic substrates would be something I'd definitely have to ask.
Best Answer
What Neil said is true, that said, you do get RF losses in PCB materials, but they stem from different mechanisms and vary in importance with the frequency of operation. For a 100MHz signal running a few centimeters, the most likely loss is actually in the dielectric material (the run-of-the mill fiberglass-epoxy material often used acts as a somewhat lossy capacitor.
Whether it's important depends on the nature of the signal and what your operating margins are. If it's a 100MHz sine wave you only have to deal with effects at 100MHz, but if you are working with a digital signal with fast rise and fall times (say to prevent metastable states, etc.) then you have to look to see how the board materials behave at much higher frequencies.
From your example the following is likely not applicable but just in case; with trace resistance effects at high frequencies you're looking at skin effect as well as surface roughness, but those really only start coming into play at GHz frequencies and then only with certain designs such as millimeter wave LNAs. Surface roughness depends on the substrate and at those frequencies you are starting to get into pretty exotic stuff, like alumina, quartz to lower the dielectric losses and reduce trace lengths, right down to having entire RF systems on a silicon substrate.