In its basic form, not particularly difficult. A copy of BIND running on an OS of your choice, a few bits of basic config and Robert's your uncle.
Gets more interesting (read complex) when you start going into running anycast DNS instances, but the average network won't need to worry about that for some time !