Google Search Links/Map
 

I've noticed for certain searches, the top website returned sometimes has additional sub-links displayed for it, and in other cases a map link. Any idea how to set this up for a site?

It appears to be auto. Ive noticed alot of places exploiting it by listing their address on their website. So when you lookup the business it list some other site not at their website.

You can get a map listing by registering your company + domain/website at Google Maps.