I want to make a map in tilemill that matches the way that labels are displayed in this example, down to the countries that get labels at each zoom level, which country gets abbrev. vs. full title, using lines to connect labels to smaller countries, etc.
That seems to be the default Mapbox label style (I notice that this Mozilla map acts exactly the same way), since there are no customizations there. However, when creating a new Tilemill map, there are no labels at all. What do I need to do to add labels in exactly the same way as that Mapbox example (i.e., the Mapbox default label styles)?
TileMill2 offers basic map data from OpenStreetMap, including labels. TM2 was also used to create Mozilla's map. You can create a map that's purely a label layer, as well as change the fonts and styling. If you're using OS X, it's suggested you build TM2 from the binary.
Note: TM2 is available as a repo and is currently a public beta. TM2 uploads to mapbox.com will be made publicly available within the coming months.