I've seen a few guides out there, but I could not get any of them to work. I can point NS records to my domain, so it sounds like I should be able to do this. I tried setting up a DMZ for the server portion, no luck at all.
There is a Java implementation that works on Windows on analogbit.com: tcp-over-dns.
The programs require the Java runtime environment 6.0+. The server requires admin port 53 access.
There is a nice article from the same author which explains TCP over DNS very well.