Derivation Theory 1: Compound

This term is long enough that it's pretty certain it's a compound. Given that the verb's meaning describes facing a particular direction, I think your intuition may be correct that this is うつ ("?") + 向【む】く ("to face a particular direction").

Origins of うつ

Regarding quite what this うつ might be, I haven't found any resources specifically discussing this word うつむく. However, there are two likely etyma (root words) -- 鬱【うつ】 ("depression, sadness") and 虚【うつ】・空【うつ】 ("emptiness, pointlessness, meaninglessness").

These might seem like the same word, ultimately, but 鬱【うつ】 is the 漢音【かんおん】, one of the later borrowings into Old Japanese, and thus has its roots in Chinese. Meanwhile, 虚【うつ】・空【うつ】 appears to be a native morpheme (sound-meaning piece), appearing in other words like うつろ ("empty space, hollowness") or うつける ("to become hollowed out"). See also the 全・空・虚 (うつ) entry at Kotobank.

Meaning shift?

As to how it is that "empty" came to mean "downward", that part isn't very clear. Semantically (meaning-wise), うつ ("emptiness, nothing") + 向【む】く ("to face that direction") could perhaps mean "to face the ground", but it does seem a bit odd.

If we look also at the 俯 entry in the Kokugo Dai Jiten at Kotobank (search the page for [1] 〘自カ五（四）〙), we see various verbs all starting with this same うつ piece. うつむく didn't appear until relatively late, cited to 1563, and it was likely influenced by earlier constructions.

The first うつ～ verb spelled with this same 俯 kanji seems to have been うつふす, showing up in texts from the late 900s. In this verb, the ふす is from 伏【ふ】す ("to bend low, to prostrate oneself"). The nature of the verb 伏【ふ】す means it can't take a directional object, so we know that the うつ here cannot function the same way it might in うつ + 向【む】く. A distant possibility might be that the うつ here refers to the original "hollow" sense, from the way that a person fully prostrate, in a posture similar to Child's Pose in yoga, is basically creating a hollowness with their body. But again, this feels like we may be stretching things too much.

Derivation Theory 2: Sound Shift

Before うつむく is first attested in 1563, we see うつぶく already in 1221. I suspect that うつむく represents a sound shift from うつぶく, much like various other places in Japanese where we see an //m// ↔ //b// shift. As such, the むく in うつむく may only be a phantom -- it's not really 向【む】く ("to face a direction") at all.

(For that matter, as described in this Kokugo Dai Jiten entry, the antonym あおむく was apparently first あふのく, as あふ from あふぐ (modern 仰【あお】ぐ, "to look up") + のく (also "to look up"), which then shifted to あおむく -- so this verb too doesn't really contain 向【む】く, despite first appearances.)

Origins: ???

That still leaves us with a puzzle, though. うつ might be "emptiness, hollow", but then we don't know what ぶく would be, as there is no such verb in any resource I can find. This might be an example of rendaku, suggesting that the latter half should be ふく instead. But that too has no likely etyma, as the verbs for ふく all have meanings that do not fit this うつぶく verb very well: 吹く "to blow", 拭く "to wipe something", 葺く "to roof a house", 振く "to shake", 老く "to get old", 更く "to get late". None of these fit well into any compound that means "to look downwards".

I suspect we may be stuck scratching our heads until and unless further historical textual evidence arises.