A well structured website will get these almost automatically, as long as you have a bit of authority
I have a 9 month old site with sitelinks. The linked pages do not all have external incoming links. My feeling is that Google Analytics data was used to choose at least some of the sitelinks. The sitelinks only appear for certain keywords, even if other keywords put me at position one. For those keywords, I know which page people tend to go to after landing on the homepage and it is those pages which have been added as sitelinks.