We have this one...
http://www.petsafe.net/Products/Fencing/In-Ground-Fences/Deluxe-In-Ground-Fence.aspx
I've installed 2 of them, one for my parents and one for myself. I've also reinstalled mine once with a thicker wire, because as previously said, the line will break! I purchased a 14 gauge wire on ebay and reran 850' of line.
A trencher may be over kill, and there is no reason to worry about hitting a power or gas line, because the line only needs to be layed 1" under the ground. If you put it down 6", you will start losing signal. I found it fastest to use a shovel to create a rivet in the ground and have a second person come behind you and push the wire into the gap. Have a big regular screw driver handy in case you missed an area and they can just push it into the ground with the screw driver. It is easiest done when the ground is wet.