Sorry I can't help toooooo much, but go to http://twit.tv, and find the Security Now podcast - they did one a couple of weeks ago on DNS - get the first one. It has a good explanation of how it works etc (which may help).
The second one on that site is about how it's been "hacked" - the first one is the how it works.
To kinda answer it:
The "root servers" (for .com for eg) hold a record for stackoverflow.com. But they can't hold all the details, so they have an NS record (name server record) saying "if you want more info, go look over there". So your machine asks that target machine (ns1.stackoverflow.com) for www.stackoverflow.com, and gets back the A record (IP address), or MX (mail etc)
So, your domain register will store it in a database or whatever they chose, and when you do an update, they SOMEHOW (I dont know, but I guess it's published by NIC, but they DO have to pay to be a registrar, and be checked out etc) push that change to the (cluster of) root name servers. They would then push the changes for your domain (eg where www goes, where your mail goes etc) to their local server, which actually serves the domain info.
Hope that makes SOME sense :)
Does this tell me that the
stackoverflow.com nameservers have
been stored in the .com name servers?
Yes and no.
Its like you going calling directory assistance for everything ending in .com. You ask for stackoverflow - they tell you "if you want SO, call this number, and they can tell you how to get Jeff (www), Joel (mail), etc.".
The root server is the first directory assistance. Your register's name server is the one on the end of the second call (assuming you called it :) )