Paraphrasing someone who does this for a living: “Exploiting vulnerabilities is a craft. Researching vulnerabilities is a black art.”
A common way of looking for vulnerabilities in software (or hardware or a combination) is fuzzing. Look at some interface and throw all kinds of garbage at it. If it keeps operating correctly (“access denied”, “syntax error”, …), try some different garbage. If it does something interesting (no response, “segmentation fault”, …), you've hit something that isn't working as intended, so investigate further to see if you've found a real problem. As soon as you find that the target isn't working as intended, and the difference in behavior has an impact on security, you've found a vulnerability, and the next step is exploitation (leveraging the vulnerability to obtain some useful result that violates the security policy).
While you can fuzz with random garbage, it's more productive to look for boundary conditions. Try sending some null bytes, or some malformed unicode, or a name containing a single quote, or a length that's just above or just under the size limit.
If you have the source code, you can perform some static analysis on it and look for common issues (unchecked array accesses, free-form strings concatenated to form a database query, …). You can also perform static analysis on a binary but it tends to be a lot harder.
To look for vulnerabilities in protocols, you can fuzz the protocol in a test implementation. Another approach is to attempt to prove some desired properties of the protocol. If you get stuck in the proof, maybe that's because that desired security property in fact does not hold.
Sometimes you can find vulnerabilities by accident, because you happen to hit a corner case and it doesn't behave as intended and you find that this has an impact on security. But it is a lot more productive to have a thorough understanding of what you're attacking. You need to know which components to look at, how to tune your fuzzer to get interesting results this century, that your proof isn't just failing because you can't find the right arguments…