A client recently asked me how they could get their site to show up like this in search results (that’s not my client, just an example I found):
The answer is disappointingly vague. From Google’s help system:
The links shown below some sites in our search results, called Sitelinks, are meant to help users navigate your site. Our systems analyze the link structure of your site to find shortcuts that will save users time and allow them to quickly find the information they’re looking for.
We only show Sitelinks for results when we think they’ll be useful to the user. If the structure of your site doesn’t allow our algorithms to find good Sitelinks, or we don’t think that the Sitelinks for your site are relevant for the user’s query, we won’t show them.
At the moment, Sitelinks are completely automated. We’re always working to improve our Sitelinks algorithms, and we may incorporate webmaster input in the future.
I also found this discussion about Sitelinks. It indicates that they have nothing to do with your site’s popularity or traffic.
If it were more important, I’d go do an exhaustive analysis of sites with Sitelinks in the search results, and figure out what makes them tick. I believe the Sitelinks only show up when you search for the domain itself (here’s an alternative example for the screenshot above, without Sitelinks), so those searchers are very, very likely to click the first result, Sitelinks or not.
DarrenBarefoot.com 
Clearly, I am way too late to help, but I just wrote more about this:
http://www.vanessafoxnude.com/2007/10/18/google-webmaster-central-sitelinks-historical-query-stats-and-surprises
Sadly, I wrote that vaguely disappointing help topic as well so I feel I must make amends. 🙂
hi
i have had this website for a while now a friend done it for me but it does not show up on searches and i don’t now how to do it please could you give me some advice i’m not very computer minded
regards Lorraine
I thought that site links would mean my site was really hot, but this puts it in perspective. I’ve got more important things to do when it comes to SEO and I’ll focus my efforts there. Thanks!
Most of our websites we produce end up showing the site navigation under search, It’s a dark art and I’m not entirely sure how it works or how we manage it but my suggestions lie both in markup and traffic
Firstly – understandable markup –
Call your navigation div “navigation” or nav, use a correct list structure using and elements if you have active states for links call your class .navactive or such like + make sure you use correct page names if your linking to news make sure the file is in a folder called news or if using dynamic content make sure you have a correct url generated by the system ie… /news/item-name… /gallery/images.
Basically make it as simple as possible for the search engine to find and spider your site while keeping naming conventions.
Secondly – Submit your xml site map to google and also make sure there is a sitemap again using good naming conventions ie.. yourwebsite/sitemap/ on your website and again this page should be produced using correct and meaningful html markup.
Thirdly – Have a popular website! If you do the above and enough people travel through your site their movement will log how the navigation structure works.
Again this is speculation as google keeps its cards close to its chest so these are just recommendations – If I’m wrong somebody tell me – however it does work for us!