Two virtual private servers (or one with two IPv4 addresses)
Internet-accessible DNS services on those VPS'
Fully synced DNS zones to prevent DNS consistency issues
Access to the domain settings interface of the domain registrar
Part 1: Creating the name server URLs (optional)
Ensure that the requirements set forth in the prerequisites paragraph above are met. This can be easily done using a hosting control panel like VestaCP.
Obtain a cheap secondary domain that you will use to set the DNS server IP addresses in. This is done to make the name servers memorable and easily recognisable.
Use external name servers for the newly obtained name server domain name. I tend to recommend CloudFlare for that, as they're great as a DNS-only service too.
Open the DNS settings of the secondary domain you just obtained. Create two A-records for 'ns1' and 'ns2' with your DNS server IP addresses in them.
Here is an example for the secondary domain name in case it would be 'mydns.xyz', with the DNS server IP addresses '192.168.1.1' and '192.168.1.2':
Save the DNS settings and wait some time for the new DNS changes to propagate. This may take 2-4 hours depending on your internet service provider and/or DNS service provider.
TIP: In the meantime, you can check the propagation of the new DNS settings over at DNSchecker.
You should now have a working ns1.mydns.xyz and ns2.mydns.xyz pointing to your two DNS server IP addresses! You've made your DNS servers memorable. 😉
Part 2: Setting-up a domain to use your VPS' DNS server
Go to the control panel of your domain registration service provider (so-called 'registrar') and open the settings of your domain.
NOTE: Do not open the DNS editor for your domain name, if applicable! The name servers need to be set on the domain name itself, not inside the DNS settings.
Set the domain name servers to the hosts you have created in Part 1 (if applicable). If you don't have any name server URLs, try using the IPv4 addresses of your name servers directly.
Save the changes you made and wait for it to propagate over the internet. This may take 2-4 hours depending on your current DNS cache and DNS/Internet service provider.