Why is the word "blue" so commonly used everywhere in Jazz: from lyrics, song titles, to record label names?
The blue note refers to a particular type of note:
In jazz and blues, a blue note (also "worried" note1) is a note that—for expressive purposes—is sung or played at a slightly different pitch than standard.
W.C. Handy, the "Father of the Blues" (an innovator who transformed the blues from an isolated folk tradition into an enduring popular-music phenomenon) defined "blue notes" as minor-key flattened thirds and sevenths over major key harmonies. As minor notes in a major mode, these were considered to have an especially mournful or haunting feel to them.
"The primitive southern Negro, as he sang, was sure to bear down on the third and seventh tone of the scale, slurring between major and minor. Whether in the cotton field of the Delta or on the Levee up St. Louis way, it was always the same... I tried to convey this effect... by introducing flat thirds and sevenths (now called blue notes) into my song, although its prevailing key was major..., and I carried this device into my melody as well... This was a distinct departure, but as it turned out, it touched the spot."
The blues is also heavily related to Jazz. It's name come from the saying 'having the blues' which relates to feeling melancholy:
The term may have come from the term "blue devils", meaning melancholy and sadness; an early use of the term in this sense is found in George Colman's one-act farce Blue Devils (1798). Though the use of the phrase in African-American music may be older, it has been attested to since 1912, when Hart Wand's "Dallas Blues" became the first copyrighted blues composition. In lyrics the phrase is often used to describe a depressed mood.
More information on the idiom feeling blue.