Leaving aside for now the few foreign loanwords (e.g., Qatar, Iraq) where Q shows up without a U, an English Q is the only letter that can't go anywhere without a partner. Why does a Q always need a U? We can blame it on a whole bunch of our alphabetic ancestors.
Because of the French
Before the Norman invasion of 1066, English didn't even have a Q. Words like queen and quick were spelled cwen and cwic. Not only did the Normans inject a whole bunch of French vocabulary into English, they changed the spelling of English words according to their French ways. French represented the 'kw' sound with QU spelling. To make things more complicated, French people stopped pronouncing the w part, but their spelling never caught up with that change, so words that English borrowed much later, like mystique and quiche, have a 'k' pronunciation instead of 'kw.'
Because of the Romans
So why did the French use QU for 'kw' sounds? Because Latin did. For the 'k' sound, Latin used a Q when it came before a 'w' sound, and a C everywhere else.
Because of the Etruscans
Why did Latin use two different symbols for a 'k' sound? The Romans got their writing system from the Etruscans, who had three different symbols for the 'k' sound: it was gamma (the ancestor of both C and G) before e or i, kappa (ancestor of K) before a, and koppa (ancestor of Q) before u or o.
Because of the Phoenicians
The Phoenicians originated the gamma, kappa, and koppa, but for them, the symbols represented different sounds. The ancestor of Q, koppa, was for a consonant made way in the back of the throat, with the back of the tongue touching the uvula. English doesn't have anything like this sound, but Arabic does, and in borrowings from Arabic (e.g., Qatar, Iraq), English represents it, appropriately, with a Q.
The road from uvular Q to quaint, quirky QU isn't as haphazard as it might seem. The 'u' vowel is produced with the tongue further back in the mouth, so 'k' is slightly further back when it comes before 'u' (compare "key" with "kook"). Q went from standing for a way-back-of-the-throat consonant to a slightly-back-of-the-throat consonant. From there, its pronunciation fate changed from era to era and language to language, but its partnership with U remained strong through the centuries, giving us a tiny window back to the origins of our writing system.