There are several ways of doing this. Normally you want more than one nameserver. They should be on different servers and even on different networks. Some TLDs actually monitor and enforce this.

Variant one - You host everything youself

So you need at least two servers, one will be the master and one will be the secondary. You configure the zone on the master and the secondary pulls the configuration.

Variant two - You host only the master and use someone elses servers as secondaries

For this you need one server and a service that acts as a secondary. With some services you can use the secondary servers for your domain and the master stays hidden.
A good and free option is dns.he.net.

Which server software should i use?

I am using NSD but you can also use bind or any other authoritative namserver. Wikipedia has a nice overview.

Just make sure the software is actively developed and has the required features. You might want to use DNSSEC.

What kind of server do i need?

Normally even the smallest VPS should be more than enough. Especially if you use a service for the secondary nameservers.
Hetzner, Netcup, Digital Ocean or Linode offer nice packages.

Here a link to instructions for installing NSD on Ubuntu.