Brute-force debugging—stepping over the code from start to finish until you see something odd, then stepping over the code from start to finish until you see the cause of that oddness, then repeating the process—will almost always work, but it may take a long time. You'll get better results by adding a bit of logical reasoning.
Don't debug randomly. Always have a goal. You should always either be testing a theory, or else gathering more information to come up with a theory. Try not to backtrack. Try to be methodical enough that each test clearly rules out one area, and then move on to the next.
If you know the code base very well, you can sometimes discover the source of bugs based on nothing more than thinking about which part of the code is most likely to produce that bug's symptoms. You shouldn't expect this to work every time or with unfamiliar code, but it works more often than you might expect.
To narrow down your search, ask yourself, "Things are working fine until WHEN?" Conceptually break the system into subcomponents and identify the first point of failure. Not only does this eliminate everything after that point, it also clarifies your thinking about further tests to narrow down the problem even more.
Beware the assumption. It's perfectly fine to make assumptions, just always be willing to reconsider them if you get stuck. Never get so locked in to a task that you forget to occasionally raise your head and consider that maybe you're going down the wrong path.
Don't be afraid of debugging a closed source system. While certainly more difficult than open systems, the example of my cell phone shows it's always possible to reason intelligently about a system—sometimes intelligently enough to understand the bug well enough to work around it.