This work considered some fundamental aspects (basics) of solving the long-term (discussed by many researchers for about 25 years) problem of “super” storage (in Maeland’s terminology) of “reversible” hydrogen (about 20–30 wt %) and “irreversible” hydrogen (about 7–10 wt %) in catalytically synthesized graphite nanofibers (GNFs). The problem was formulated in connection with the experimental results (obtained by Rodriguez and Baker’s group), which were patented and published in 1997–2005, and which other researchers could neither reproduce (except, to a certain extent, Gupta’s group (2000–2006)), nor reveal their physics. A deeper study of this important problem and the identification of a number of fundamental (including kinetic and thermodynamic) aspects of solving this problem were made using a modified efficient method for processing and analyzing the hydrogen thermal desorption spectra and their related thermogravimetric and other data. For the first time, the characteristics of the main desorption peak of irreversible hydrogen in graphite nanofibers, which correspond to a first-order kinetic process, were determined both from thermal desorption and thermogravimetric data. These characteristics were the temperature of the highest desorption rate (Tmax = 914–923 K), the activation energy of the desorption process (Q ≈ 40 kJ/mol), the pre-exponential rate constant factor (K0 ≈ 2 × 10–1 s–1), and the amount of the released hydrogen (~8 wt %; i.e., the atomic ratio H : C ≈ 1). The physics of the processes of super sorption of irreversible and reversible hydrogen was analyzed, including the role of hydrogen diffusion processes accompanied by the “reversible” capture of the diffusant by certain sorption sites, the role of the hydrogen spillover effect causing the local atomization of gaseous H2 during the GNFs hydrogenation, and the role of the Kurdyumov phenomenon of thermoelastic phase equilibrium. It was shown that the above extraordinary data on the super storage of hydrogen in GNFs are neither an error, nor a hoax, as most researchers believe. The necessary conditions for reproducing these extraordinary results by other researchers were determined. It was shown, in particular, that Rodriguez and Baker’s group can reproduce the “normal” results (about 0.1–4 wt %) on the storage of hydrogen in GNFs obtained by other researchers.