With some minor caveats, it actually is as easy as changing the record at your registrar. Here's a high-level overview of what needs to be done, in what order, and some things to looks out for:
First, make sure the new server is responding to queries and is getting updates as it should. Once you've done this, change your local records to reflect the new address of the new server. Starting at this point, you will need to make sure you keep all three servers in sync with any zone updates. Any divergence, especially if the new server doesn't get an update, could have negative consequences down the road.
Now, go change your NS registration with your registrar (e.g. Network Solutions, GoDaddy, etc). This will probably involve editing a "nameserver record" (that's GoDaddy terminology, which I know because I use them) - more commonly this is called a "glue record". Once this is done, you wait. It usually takes 24 hours for this to propagate fully. At this point, you will start seeing some queries hit the new server, but you must keep the old server online since some queries will also be hitting it.
Once the 24 hours period is over (that period may be different, consult your registrar for how long they make it), you should then wait for the TTL to expire on all your records. This is commonly a week, but is determined by the TTL definition in your zones.
After the TTL wait, you should be able to turn off your old server, since all new queries should be going to the new server (or the one that wasn't changed). If it were me, I would wait another TTL period before doing so, simply because I'm paranoid, but that's a personal choice, not a requirement.
You can validate what you're calling the "nameserver registration" process several ways - my preferred method is to issue a
whois <domainname>, which spits out your nameservers of record (among other information). You should see two nameservers - if you see the one that's not changing and the old server, wait 12 - 24 hours before re-querying. If after the time specified by your registrar you don't see the change, you need to either redo the change or you need to talk to your registrar for help.