How do I set them up, am I right in thinking I can create A records for NS1.domain.com to point to their IP?

Wrong section :D

Matrix28, though as pointed out this is in the wrong area, give us a bit more detail as to the server's setup, is it running any control panels? if so which? what type of operating system? information like that will greatly improve our ability to help.

http://forums.webhostdir.com/showthread.php?threadid=4502

That thread seems very useful with regards to registering nameservers.

Thanks for that link, if anyone else would like to help then I am running windows and no control panels.