The neural correlates of exploration and cognitive mapping in blindness remain elusive. The role of visuo-spatial pathways in blind vs. sighted subjects is still under debate. In this preliminary study, we investigate, as a possible estimation of the activity in the visuo-spatial pathways, the EEG patterns of blind and blindfolded-sighted subjects during the active tactile construction of cognitive maps from virtual objects compared with rest and passive tactile stimulation. Ten blind and ten matched, blindfolded-sighted subjects participated in the study. Events were defined as moments when the finger was only stimulated (passive stimulation) or the contour of a virtual object was touched (during active exploration). Event-related spectral power and coherence perturbations were evaluated within the beta 1 band (14–18 Hz). They were then related to a subjective cognitive-load estimation required by the explorations [namely, perceived levels of difficulty (PLD)]. We found complementary cues for sensory substitution and spatial processing in both groups: both blind and sighted subjects showed, while exploring, late power decreases and early power increases, potentially associated with motor programming and touch, respectively. The latter involved occipital areas only for blind subjects (long-term plasticity) and only during active exploration, thus supporting tactile-to-visual sensory substitution. In both groups, coherences emerged among the fronto-central, centro-parietal, and occipito-temporal derivations associated with visuo-spatial processing. This seems in accordance with mental map construction involving spatial processing, sensory-motor processing, and working memory. The observed involvement of the occipital regions suggests that a substitution process also occurs in sighted subjects. Only during explorations did coherence correlate positively with PLD for both groups and in derivations, which can be related to visuo-spatial processing, supporting the existence of supramodal spatial processing independently of vision capabilities.