So what are the rules for using that. For example "When I heard that it was done by the same two that did The Wire I figured that it would be worth it."

The second that is correct, but is it okay to not use the first or third? Just want to conserve precious keystrokes.

The first and last you may safely omit (in fact, I believe omitting them is preferred usage -- those "that"s are implied ;-) ...

The second "that" you can also replace with "what," just to make Carp happy =D