Murder Mysteries become available after you visit with Vidocq and Charles Cochon de Lapparent for the first time in the Palasis de Justice district. Arno Dorian can now come across various murders and work to solve them. No Murder Mystery will be directly revealed on the map unless you have passed fairly close by its starting location.
Each of these missions are investigation oriented. There is overall minimal combat. Just whoever you manage to agitate on the way over or pick a fight with. Each Murder has its own set of locations. Be sure to visit each of the scenes for the murder (there is a counter for the case locations). Each of these locations will also have a number of clues attached to it. Take your time to fill it out to get the full picture of the crime and figure out who did it. Getting it right the first time nets the best pay reward. The weapon is always given.
While they have scaling difficulty, they are unrestricted by Arno's present level. All of them can be completed as early as the beginning of Sequence 3. This allows Arno to get access to some powerful weapons fairly early on.
Look for this symbol on the map: