Who needs indoor plumbing when for less than $300 you can have a perfectly good outdoor crapper. Check your local laws.
Step 1: The foundation
A good foundation is the key to a good outhouse. Dig a hole about 4' deep, 3.5x3.5ft square. Make it a good hole with even sides because you'll have to line it.
One point about soil. If you have hard clay soil, make sure that the drainage around the outhouse is good to avoid too much water getting in, because it won't want to leave (this could cause splashback).
You've got your hole. Drop a wooden box with tarpaper wrapped around it in the hole to keep moisture out. Level and even out the ground around the hole and place a foundation made of treated 4x4s around it. The foundation will for this one was 4'x3.5' (this allowed a 4x8 sheet of plywood to be cut at 3.5ft, one piece for the floor and the other for the roof with an over hang. 4'wide on the floor and 4' deep for the roof).