Simply: who are Alice and Bob, and why are they mentioned in every Bitcoin-related article I read about that talks about Bitcoin transactions?
What is the history or mystery of these two?
Fictional characters. Cryptography (and other) books use names like that often.
Alice and Bob are placeholder characters corresponding to the letters of the alphabet. They are used especially in computer science to describe use-cases or scenarios. The scheme is used because it's more convenient to say "Alice sends money to Bob" than to say "Party A sends money to Party B". As each name has a different initial, diagrams can fall back to single letter labeling.
It's a well-known meme:
via xkcd.com
The list usually goes something like this: Alice, Bob, Charlie, Dave, Erin, Frank,…
Other names are used to represent attacker types or other recurring roles: