Who do I contact to have the property line marked?
The official answer is find a local land surveyor and hire them to do a property survey.

However, you can do a bit of research on your own, and may be able to figure out where the property lines are well enough to get by without hiring a surveyor, which can cost $250-1,000+, depending on the size of your property and how complicated the boundaries are. Note that you and you alone will be responsible for the cost of moving your fence if you get it wrong though.

Property corners are usually marked by a piece of rebar driven vertically into the ground. There's often a brightly colored plastic cap on top as well. If you're lucky, the text description may even be legible.



You can get a good idea of where to start looking by getting a copy of your plat at your local courthouse.

Tools you'll need:


metal detector (or a very strong magnet on a stick, as DMoore suggests)
shovel (I'd recommend a drain spade, but you can get by with most any shovel)
compass
100' tape measure


Then go about finding your property corners. They should be fairly easy to pick up with even a cheap metal detector, as they usually aren't buried very deep, and are made of a giant metal bar. Try triangulating off of known features, like curb or street corners. Roads often have centerline markers embedded in them as well that you can reference.

To keep from having a bunch of obvious holes in your yard, cut a plug of soil around the suspected marker location by digging the shovel in a circle to cut the sod.

Source: I used to be a land survey technician for a few summers in college.