The record gets delegated from the parent nameservers - it's like a chain (or usually described as an inverse tree.) Every DNS client knows the IP addresses of the root servers - these are a set of servers (I think it's 13) that provide the IP addresses of the registries' servers - Nominet for .uk, eurID for .eu etc.
Your domain is then registered with the registry who have the addresses of your nameservers (ns1.oldserver.com in your example.) Finally your domain's nameserver (or nameservers as you should have two minimum) serve the actual request.
Imagine for example, a client wants to visit www.domain.com.
This can be split into three components - the so-called top-level domain (TLD) which the client queries the root servers for - .com in this example. One of the nameservers that would serve this might be a.gtld-servers.net - the root servers will give the IP address of a.gtld-servers.net to the client - these are known as the NS and glue records.
Next is the actual domain - domain.com in this example. The client queries a.gtld-servers.com for domain.com. This may then give back ns1.domain.com and ns2.domain.com with the relevant IP addresses as the NS and glue records.
Finally the hostname - www in this example. The client will therefore query either ns1.domain.com or ns2.domain.com for the domain www.domain.com, and get back the actual IP address of the website (A record.)
All this takes place in milliseconds. The typical timeout for a DNS resolver is 2 seconds.
To go back to your original question, when you change the nameservers, you're changing the NS records at the registry-level (Nominet, eurID etc.) After your change is made, when a client queries the root servers for domain.com, it will get given the IP address of ns1.newserver.com instead of ns1.oldserver.com.
It typically takes up to 72 hours for all clients around the world to notice the change, because they cache all results for a length of time specified in the domain record. NS records are usually cached for 72 hours or even up to a week. Therefore don't take your old name servers offline for at least a few days after making the change.
Changing an A record is much the same as changing an NS record - you're only changing the content, like changing a database record. The next time someone queries for your record, it'll get the new value (again taking into account caching, but it's much lower for A records, usually 1/2 - 1 day.)
If you've got access to a Linux box, run dig +trace www.google.com, and you'll see the full chain of queries which might give you a better idea.
