When you say Navigation Providers I assume you are referring to sitemapproviders. Basically sitemapproviders are code that determine the navigation. I have written quite a few of these to provide better navigation in SharePoint. SiteMapProviders will be asked by the Menu Control through the Datasource different things. The breadcrumb menu control will ask for the current node and then for each node that is returned it asks for the parent node until null is returned. The Top Nav menu control will ask for the root node, and then for each node that is returned, the menu control will ask for it's child nodes until the static or dynamic level is reached. I wrote a blog article about this a few years ago located here. I provide some sample code for writing a sitemapprovider. The code I provided has some issues with it and is not optimized but it can help you get started.
As far as datasources go, that's a typical thing in data bound webcontrols. You can assign the datasource of a control to be a sqldatasource, or a dataset, or in this case it's a sitemapdatasource. It basically converts the sitemapprovider data into something that the menu control can understand.
And yes the menu control just renders the UI. There is a special sharepoint menu control called aspmenu. The source for this control was distributed on the sharepoint blog a few years ago.
I hope all of this makes sense and answers your questions.