Lately, it seems that many people have begun to champion the benefits/necessity of building tests.

For me there is no "lately" about it. I have always championed the concept of testing suites for software for anything more complicated than a one liner.

The methodology that I use for testing is a simple one. I ask myself the following quesitons:

1. What is the base functionality of this software?
2. How do humans interact with it?
3. How can I simulate that?
4. How can I simulate the interactions going wrong?

Once I've answered those questions for myself I proceed to develop a test plan and that most of the time will drive how I write my test suite.