Feminine / Masculine History
How were nouns made either masculine or feminine? For example, what made a suit masculine but a tie feminine?
Grammatical gender doesn't really correlate with any natural gender. It has more to do with the structure of the word (almost always its ending) than with any male-ness or female-ness of the item in question. In languages that decline nouns for cases, like Polish, German, Latin or Icelandic, grammatical gender plays a bigger part than it does in languages that are not heavily inflected, like English, French or Spanish. The words change (in most cases, the suffix or ending) depending on what sort of function the noun has within the sentence - subject, object, indirect object, possessive and the like. In those cases, the nouns change alot like how the verbs change in French.
If you mean on English then it's a consequence of Old English which used genders. From the 11th century on the gender usage began to decline in English. It's a matter of tradition that some inanimate things in English now can be referred as with 'he' or 'she'.
If you mean on another languages, such as Romance or Slavic ones, then a noun's gender is determined by its ending.
If I had to guess, I think it had largely to do with the musicality of the words (esp the endings) and the connotation that certain nouns had (Moon being thought of as female or whatever because of myths surrounding it). This is not authoritative, of course, but I think that explains why so much of it is seemingly random and yet, when you say it in a language, it "sounds" right.