Since most people understand "science" as "good" and "not science" as "a system of mystical thinking akin to Zoroastrianism", just questioning whether something that's called a science is "really" science is guaranteed to offend the people who practice it, contrary to your hope that no one will be offended by your question.
I somewhat sense that you don't know much about linguistics, and your image is of prescriptive linguistics, i.e. a bunch of guys sitting in an ivory tower and making pronouncements forbidding prepositions at the ends of sentences. This is not what linguists do; that sort of thing is usually found in English and modern languages departments. You similarly misunderstood computer science, as Ben Crowell addresses in his answer. If you look into things a little, you'll find that modern linguistics is "scientific" in lots of ways.
Many linguists do field research. This involves living among the speakers of unrecorded languages, learning and describing these languages, and helping to analyze the impact these languages have on currently held theories. This is fully as scientific as what cultural anthropologists, sociologists, and behaviorists of all kinds do.
But where do linguistic theories come from? Linguistic theories, for the most part, are either psychological theories, attempting to make sense of human language as an activity of the human mind, or mathematical theories, developing formalisms that describe the structure of language. Noam Chomsky's formal language hierarchy and generative grammar are mathematical formalisms that are also used in computer science, which you also malign as not a science. More recent theories, like lexical-functional grammar, are even more mathematical in character. These mathematical formalisms describe the syntax of human language, and books on them contain proofs, as do most books on computer science per se, and not programming. Set theory is also used in some corners of semantics.
Statistics is frequently applied in linguistics; see for example this paper. The answer to your question "how do linguists' methods for reaching consensus differ from historians'?" is that linguists make use of statistical data, try to explain things within existing theories, and apply mathematical formalisms, similar to the way economists and physicists reach consensus. And linguistics continues to get more mathematical, by incorporating statistics, probability, and computer science into its theory and practice.
Finally, have a look at historical linguistics and comparative linguistics. Modern linguists' painstaking reconstruction of the Proto-Indo European language, the common ancestor of languages as widely sundered as English, Latin, Armenian, Persian, and Hindi, cannot, in my opinion, be called anything other than a work of science. There were judgment calls; there were ambiguities to resolve; there are competing models; and there are some things we'll probably never know. But that's also true of paleontology, geology, and astronomy, and no one disputes that those are sciences.
As Jangari says, there is no sharp dividing line between "science" and "system of mystical thinking". Entire books have been written on this question. You can read them, and decide for yourself on the question of law. But if you believe that a field's methods and intentions make it scientific, and if you accept that cultural anthropology, economics, sociology, statistics, mathematics, computer science, paleontology, geology, wildlife biology, and physics are sciences, then linguistics is a science.
(I tried not to be offended, but as a computer science major / linguistics minor who considered law school, your apparent ignorance of computer science and linguistics touched a nerve.)