I believe I have seen this on the the blog once before but I can't seem to find anything about it right now.

How does Google choose which links to put as a subset of a main domain in the search results. For instance if you search for Microsoft, indented under the first result are:

Download Center –
Help and Support –
Jobs – Locations – Global Careers –
Windows Home Page –

Is this something accomplished by Google Sitemaps? Good web design? A combination? Or is this something that Google secretly figures out themselves.

Here's a thread about it from August 2005 (in which you posted, BrianS):

http://blogoscoped.com/forum/9944.html

As I said back then, I don't think it's got anything to do with Sitemaps. (Or it definitely didn't used to be, at least.)