According to this interesting 2003 Straight Dope column, people who are born deaf can and do indeed think linguistically, but in some form of gestural language rather than a spoken language.

The profoundly, prelingually deaf can and do acquire language; it’s just gestural rather than verbal. The sign language most commonly used in the U.S. is American Sign Language, sometimes called Ameslan or just Sign…

…Sign equips native users with the ability to manipulate symbols, grasp abstractions, and actively acquire and process knowledge — in short, to think, in the full human sense of the term.

…The answer to your question is now obvious. In what language do the profoundly deaf think? Why, in Sign (or the local equivalent), assuming they were fortunate enough to have learned it in infancy. The hearing can have only a general idea what this is like — the gulf between spoken and visual language is far greater than that between, say, English and Russian. Research suggests that the brain of a native deaf signer is organized differently from that of a hearing person. Still, sometimes we can get a glimpse. [Oliver] Sacks writes of a visit to the island of Martha’s Vineyard, where hereditary deafness was endemic for more than 250 years and a community of signers, most of whom hear normally, still flourishes. He met a woman in her 90s who would sometimes slip into a reverie, her hands moving constantly. According to her daughter, she was thinking in Sign. “Even in sleep, I was further informed, the old lady might sketch fragmentary signs on the counterpane,” Sacks writes. “She was dreaming in Sign.”

This meshes nicely with Rand’s observation in the Appendix to Introduction to Objectivist Epistemology on “The Role of Words”:

So the word is not the concept, but the word is the auditory or visual symbol which stands for a concept. And a concept is a mental entity; it cannot be perceived perceptually. That’s the role played by words.

…One’s mind first has to grasp the isolation and the integration which represents the formation of a concept; but to complete that process — and particularly to retain it, and later to automatize it — a man needs a verbal symbol.

…Now observe an interesting issue: a case like Helen Keller. She couldn’t use either auditory or visual symbols. She had to be taught tactile symbols. She had to learn some mental condensation, some form of perceptual substitution or perceptual shorthand in order to be able to grasp the perceptual world at all. She had only tactile means. And she learned, and she was able to communicate, even to think and write. But prior to the time of learning this type of physical symbol, she was not able to grasp or deal with anything [conceptually], as far as could be observed. Therefore I wouldn’t say the symbol has to be auditory or visual. If a mind is born handicapped in a certain way, there can be a substitute. Assuming a healthy child, the auditory and visual symbols are the easiest and the most productive. You can do more by that method. But some other method has to do if a person is handicapped.

The principle here is that in order to deal with a wide range of knowledge, you have to reduce the concretes to a single concrete, a concrete of a different order, a symbolic concrete.