九州という言葉は廃藩置県の前からありますので、県が由来ではありません。
旧国名は略して州を付けて呼ばれる事が一般的でした。
その州が九つで九州です。
ここまでは#1さんとほぼ同じ答えです。
でもこれは私の中では少し釈然としません。
旧国名は呼び方のゴロの良さで「○○の国」と呼ばれたり、「○州」と呼ばれたりです。
例えば
紀伊(きい)という国は紀伊と呼ばれる事は滅多に無く、紀伊國(きのくに)と呼ばれたり紀州(きしゅう)と呼ばれたり。
長門(ながと)の場合は長州(ちょうしゅう)呼ばれる事が一般です。
旧国≒州です。ほぼ同じ事です。
でも、州の方が単位が大きいです。
大きい州は前・後、または前・中・後で分割されて国になっています。
薩摩の國=薩州ですが、
筑前の國も筑後の國も筑州です。
九州にはそういった州を分割した国が複数含まれているので「九国」であっても「九州」では無いと思えます。
同じ様な呼ばれ方をしている四国はどうでしょうか?
こちらは「四国」であり「四州」でもあります。
九州と四国の呼び名が逆(九国と四州)か、単位の統一があれば(九国と四国)納得しやすかったのですが、一番イケてない組み合わせなので釈然としません。
結局は、昔も今も大衆は物事の本質より呼び方のゴロの良さを重視するという事です。
突き詰めると崩れるが、なんとなく九つの州から成り立っていそうなので、九州と呼ばれたら定着したという程度にしか思えません。