Don't roll! I hardly ever require people to make investigation rolls or such when running this type of campaign. You want to reward clever thinking and good roleplaying. Don't let a bad roll hinder a good idea. Also, you don't want to give away the farm just because a player rolled really well.
What I like to do is outline the basic structure. Plan out the number of steps the player can use to get from the beginning to the end. Here's an example:
Step 1: The setup. Learn about the mystery and are provided one or two introductory clues (which, ideally you should have to work for). A client comes into the private investigator's office and asks for help. The PI gets the clues by asking the client the right questions.
Step 2: Legwork. This is where the real investigation starts. Hopefully using a lead obtained in step 1, the PC goes and talks to someone who may have information, investigates the scene of a crime or does some surveillance.
Step 3: Run-In. It's often fun to throw in a little action/combat encounter with someone who may have a clue on them or know some useful information. It's important that the character's earn any clues by defeating the bad guy and competently interrogating him afterward. I let them make rolls once in a while, but I primarily judge the outcome on what questions they ask. In other words, if you roll well for interrogation but only question the guy about red herrings, he'll only tell you about red herrings. If you roll poorly but ask the right questions, he'll point you where to go, but won't fill in any other important details.
Step 4: Conclusion. This is where the clues lead to the end of the road, or at least to a big climactic final battle or social conflict where the truth will be revealed at the end.
Depending on the players, I may throw in another legwork step, to make them work harder and prolong the investigation. This would be good for a small game with only one or two players but with a larger group, it's tough to get them to take too many steps to get to their goal.
Now with each step, I try to come up with at least two or three clues that will lead them to the next step. For instance, when searching for a missing piece of art, the PCs can speak to someone in the art community who knows what is coming and going illicitly, or they could talk to someone in the crime community to know who has been making a lot of heists lately or finally, speak to someone with divination magics who might be able to help.
Lately, no matter what I lay out, my players choose an option I hadn't thought of, in which case I improvise a way for them to find whatever clue they need to get to the next step (if their idea seemed like a reasonable one).
One final note is that each of the steps need not be the same depending on the course of action the players choose. One avenue of investigation might lead to a totally different step 2 and 3 then another approach. The only important thing is that the number of steps should stay about the same, to keep the story properly placed.
So there's my method for running a mystery. Hopefully some of it will be helpful to you!