Your server needs to have a static IP address. Once you have that, and have your DNS service set up, then you should be able to update your domain(s) to point to the new DNS. This new server doesn't have to be your primary DNS entry for the domain(s), but it should be one of the first two entries. And that's pretty much all you need to get started.

One other consideration is setting up the master/slave status of your DNS servers so you only have to make updates in one spot (helpful to ensure everything stays in sync). This isn't a requirement, it just makes your life easier.