The formal definition states that it's the distance between two quantum states. What does that mean experimentally? Does distance here mean the distance between two states on the Bloch Sphere? I am a little confused about the meaning of gate fidelity.
Fidelity is a distance measure between quantum states. The gate fidelity uses fidelity to decide how noisy a quantum gate is.
Take two copies of a state, apply your implementation of a gate on one copy and apply the ideal gate on another copy (this can be done on paper, not in a lab) and compute the fidelity between the two outputs. This is the gate fidelity. There are some subtleties on what state you should use in this comparison but this should be made clear by the author.
See the discussion in Section 4 of this paper.
Very briefly, gate fidelity refers to a way to compare how "close" two gates, or more generally operations, are to each other.
As discussed e.g. in (Magesan et al. 2012), if one wants to compare the action of an operation $\mathcal E$ and a gate $\mathcal U$ on a given state $\rho$, one can define their "gate fidelity" as the quantum state fidelity between $\mathcal E(\rho)$ and $\mathcal U\rho\mathcal U^\dagger$.
A related notion is that of average gate fidelity, which is defined as the above but averaging over all states $\rho$, and thus gives a better quantifier of how similar the operations themselves are (as opposed to just comparing their action on a single input state). See the paper above for more details.
I find the above answers correct and sophisticated. My explanation would give you just a very general understanding.
In order to understand gate fidelity, you have to know the difference between a physical gate and a software-visible (logical) gate. Due to the current hardware-technology limitations, physical gates (those that are implemented physically on the real quantum devices) do not precisely map to (implement) the logical gates.
The difference between an ideal gate (a logical gate) and what the corresponding physical gate that a quantum hardware offers is called gate infidelity.