Sorry I can't offer you a tutorial, but take a look at the tests that come with OpenGuides and the CGI::Wiki family of modules. You should be able to find examples of the kind of scenarios your wiki formatter needs to cope with, especially as we were doing very much the same job.

This highlights an interesting design point, in that if you separate the text munging from the web stuff, you can write tests that don't rely on having Apache running, let alone configured.

Basically, I don't want to test for things I know. I want to test for all the possible arbitrary text that users could throw, and see if my module can format it to valid html in the manner that the users expected it to do.

That's a toughy. You DO want to write tests for things you know - this is a starting point. In terms of all possible text, this is fairly intractible. Consider the documentation. The pod that goes with the module gives examples of how to use it - these examples should be included in the tests. For the more esoteric scenarios, my advice would be to get a project team or an on-line community together, inviting feedback from as many tech-savvy users as possible. Every time you find something that misbehaves, write a test for it.

Good luck with your module