Step 1: Dig The Hole !!!
Our hole measured roughly 2'(l), 1'(w), 1'(d). We tried to keep everything pretty square, but that's only because we're slightly anal and I don't think it's that important in the great scheme of things. We made sure we kept the pile of excavated earth near to the pit so that it was close at hand when we needed to bury our feast!
N.B. At this point you may want to make sure that any nosy neighbours etc. haven't got the wrong idea about this hole in the ground you're digging; police searches and BBQs rarely mix!