While I can make a guess that a prison cell is a small hollow place (of sort) and hence further a police station may be called a nick, I'm puzzled as to the meaning to steal. How could it have come about?
It's an unclear mess.
The OED lists all these senses of 'nick' under "nick, v.2", which is the verb form of "nick, n.1", meaning 'tally' and 'tally mark'. The noun and the verb show up together in the mid-15th century with no obvious etymon but rapidly spread to cover senses ranging from female anatomy to screwtop notches to precise moments to winning throws in dice games.
The illicit senses of 'nick' start in the later 16th century in reference to what was later 'chiseling': cheating or defrauding debtors and the poor for one's own benefit (sense III.15.a).
How doth he nick the debter now by hault exacting wayes.
The OED considers Sven's earliest quote from Fletcher's Mad Lover to be an example of this sense, not anything about theft.
From there, it was used by the early 17th century in reference to a rapid strike, catching someone unaware (sense III.16.a). This was used in reference to gulling marks but also catching the conmen at their own game.
We must be sometimes wittie, to nick a knave.
That's the sense that eventually became the British slang for 'arrest'.
It seems like a sense of successful and skillful theft, hitting at precisely the right moment, should have arisen pretty naturally from all those other senses, but the OED gives the first clear citation of 'nick' meaning 'to rob' (III.16.b) as David Anderson's 1826 Scottish poems:
Some there ha'e gotten their pouches picket,
Their siller an' their watches nickit.
Similarly unexpectedly late is the use for jail (sense 15), which shows up in Australia in a book of Sydney slang from 1882:
Nick (The), gaol.
This doesn't have any relation to cave or hollow; it's much more likely a loconym created out of the action of arrest. Personally, though, I'll maintain the head canon that some literate degenerates derived it via "Nick, n.2" and "Old Nick, n." from "Old Iniquity", apparently a set figure in early modern morality plays.