In my post Unit Testing and Assumptions, I described my ideal type of test: "I don't care how [the algorithm does] it, just that the output is what I expect. These tests are short, easy to write, and they make no assumptions about the underlying code." What I didn't realize at the time is that I was simply making the case for state-based testing.
State-based testing focuses on the results of a computation, not on the specific steps of an algorithm. Instead of verifying that add(2, 2) was called on a mock, for example, we simply assert that the result is 4. This makes the tests less brittle and usually easier to write because of less setup. It's also better from a TDD perspective since you don't need to know the details of the code-to-be-implemented in order to write your failing test. For better or worse, these type of tests can quickly turn into "mini-integration" tests since they lack the test isolation that mocks provide.
State-based testing stands in contrast to interaction or behavioral testing. Here the focus is, well, on the interaction of the system under test with a mock object. This can be useful when the method delegates some work to a collaborator. The collaborator object is already tested, so we just need to verify that the delegation takes place with the correct parameters. Indeed, this is essentially the only way to unit test code that makes calls to a web service or database. The downside, of course, is that the test locks down the behavior of the code. If that behavior ever changes, even if the results stay the same, we must update the test accordingly.
I tend to be a proponent of state-based testing whenever possible. I use it in cases where my class under test has no collaborators, or when the collaborators are lightweight. I like that this type of testing encourages return values over side-effects. I'm also usually more concerned that the results themselves are correct than how the code computed them.
If I have a good reason to isolate the class completely, then I use mocks to verify behavior. This is usually on the seams of the system, such as near the data access layer.
Ultimately, I end up doing whatever feels right at the time given the situation.