Gender is a grammatical feature that was present in Proto-Indo-European, that is, the common ancestor of a diverse group of languages including both English and Spanish, as well as Greek and Hindi. The development of that is an interesting read.
Both Anglo-Saxon and Latin (the languages from which English and Spanish derive) had a three way gender distinction, masculine, feminine, and neuter. Along the way, English lost it, now only making a minimal distinction in animacy. You can see the process of gender loss by looking at Danish, another Germanic language, which depending on region has one, two, or three genders.
Most languages derived from Latin lost use of the neuter gender except under highly specific situations. It seems to me (don't quote me) that most neuter words switched to masculine in the development of Spanish. Romanian has a neuter, but it means that nouns function as masculine in singular, and feminine in plural. Asturian likewise has neuter, but primarily uses neuter for uncountable/mass nouns, though it does have its own ending.
Grammatical gender is really just a special type of noun-classing, which is common in many other languages (if you think two or three genders are hard, try Zulu with fifteen genders/classes!). Looking at Bantu languages (of which Zulu is a member), one might be able to hazard guesses as to the origins of gender in PIE in terms of semantic categorization.
If you're more curious about how a given new word in Spanish acquires its gender, that's a pretty complicated topic. Most imported words are masculine, unless the language the word came from has M/F gender and then it tends to preserve that gender, but not always. Sometimes, a word will be imported and obtain two different genders based on region (el/la Internet, el/la computador(a)), so there's no single rule. Sometimes a word I might make up just sounds like it should be one gender or another, but that's pretty subjective.