How is 海 related to 腦? Why does compounding sea/ocean (海) to brain (腦) mean mind (腦海)?
I am going to answer this from its origins. It comes from 《灵枢经·海论》 with the sentence “人有髓海，有血海，有气海，有水谷之海……脑为髓之海。”.
In traditional chinese medication, it is believed that the brain is a sea of marrow, hence the name. "中医学认为脑为髓海，故称。" (Somewhat similar to the idea of a metaphor, though)
Similar ideas have been referenced in ancient Chinese writings to prove this origin:, for instance:《素问·五藏产生论》：“诸髓者，皆属于脑”。
// I am going to edit to answer some questions:
Firstly, to answer LilyWhite's question. Why is it not 髓海，but 脑海 that we use?
It's because they later start to mean different things. The concept comes from traditional Chinese medicine, but other writers started using the word 脑海 in their writings to represent the organ of memory and thought, which indeed popularized this meaning than the traditional medication meaning. For example: 叶紫 《丰收》九：“十五六年农民会的影子，突然浮上了他的脑海。” 茅盾 《喜剧》二：“立刻他的脑海中展开一张政治地图了。” etc.
When we now say 髓海, it means the traditional Chinese medicine meaning, one of the four seas in the human body -- which is the brain, sea of marrow.
When we now say 脑海，it usually means the organ of thought and memory, smth like that.
So to answer @user 's question: Why is it a sea of marrow?
Well, in traditional Chinese medicine theory, there are four seas in the human body. The other ones are 血海，气海，水谷海.
There are supposedly 3 types of marrow, from the bones, the spine, and the brain, all supposedly formulated from the essence of your kidneys, "骨髓、脊髓、脑髓,均由肾精所化生"
The bone, spine produces the marrow, and the brain is where the marrow accumulates. There is an old saying, "肾主骨生髓,脑为髓之海", which could be understood as if your kidney works well, then your bone can produce sufficient marrow for the brain, which makes you healthy and lively. "肾精充沛，髓海满盈，脑得其养，则精力充沛".
It's just theory, nothing more, i have no idea why our ancesters thought it was a sea of marrow but not a sea of bone or blood (guess they had autopsy then)