Foreword: this doc assumes you are using BIND version 8 or later. I will eventually expose more DNS concepts, so that people using different setups can more easily adapt these directives to their configurations. As usual, feel free to send questions to, or to the mailing list :

How do I resolve names in the NX VPN?

or: How do I setup DNS ?

You have many choices :

Okay, I decided to host my own SLD (Second Level Domain), say foobar.nx ; what do I have to do?

You must configure BIND as explained above, specifying that you will be a master DNS for foobar.nx, with a zone directive. You must also build a db.foobar.nx zone file. Here's a short example :
$TTL 604800
@       IN      SOA     bigserv.foobar.nx (
                        2000090403      ; Serial
                         604800         ; Refresh
                          86400         ; Retry
                        2419200         ; Expire
                         302400 )       ; Negative Cache TTL
                NS      bigserv
		NS	littleserv
		MX 20	mailserv
		MX 10	mailhub.quux.nx.
bigserv         A
firewall	A
bigserv		A
littleserv      A
mailserv        A
;available      A
;available      A
;available      A
gamemachine     A
www             CNAME   mailserv
ftp             CNAME   bigserv
irc             CNAME   bigserv
dollywoops      CNAME   dollywoops.quux.nx.
www.panda       CNAME   www
$TTL 3600
dynamix         A
dhcp            NS      dynamix
Okay, this is a really tricky zone. Let's review it step by step : Please note that when specifying host names, if you want to refer to an host outside of your zone, the FQDN should end with a dot. If you write
gator CNAME ali.gotham.nx
you will end up with gator pointing to ali.gotham.nx.foobar.nx, which is almost certainly not what you want.

Last word : when a line doesn't start with a name, BIND considers you want to repeat the preceding name. If you want to refer to the zone itself, use the special name @.