I was under the impression the word came from the Latin 'tri' (three) and 'via' (road). Basically, bits of information and news were posted at crossroads (where three roads met, I suppose), hence the word.
The crossroads was a trivium. Trivialis comes from this, and is a word meaning trivial, commonplace etc. The word trivial is derived from this, and appears in the 1580s. Trivia as a word on its own dates to about 1920, and is a back formation.