Sixty deaf and hearing students were asked to search for goods in a Hypertext Supermarket with either graphical or textual links of high typicality, frequency, and familiarity. Additionally, they performed a picture and word categorization task and two working memory span tasks (spatial and verbal). Results showed that deaf students were faster in graphical than in verbal hypertext when the number of visited pages per search trial was blocked. Regardless of stimuli format, accuracy differences between groups did not appear, although deaf students were slower than hearing students in both Web search and categorization tasks (graphical or verbal). No relation between the two tasks was found. Correlation analyses showed that deaf students with higher spatial span were faster in graphical Web search, but no correlations emerged between verbal span and verbal Web search. A hypothesis of different strategies used by the two groups for searching information in hypertext is formulated. It is suggested that deaf users use a visual-matching strategy more than a semantic approach to make navigation decisions.