When Google introduced Sitelinks, it attended to navigational searches. It's not always when you know the URL you need to type, and by being the biggest search engine in the world, the Mountain View-based company had to address this special category of searches.
Sitelinks provide users with a more in-depth approach, providing links
to the various pages and tabs found on the main site of the queried item. In other words, the option gives an 8 to 10 link long list of popular places to be found on the site. Google said when the feature was added that it was a big step forward to optimizing the search experience and even a big time saver.
The Navigational Search Boxes that have been added are a means of going even deeper into the content of the site than the Sitelinks. It actually displays a search box for the specific site, as shown in the screenshot on the left. Note that it is not available for all the sites, but rather for the more important ones or most popular. With the example, I've tested Arsenal F.C.'s homepage and Barcelona F.C.'s and the latter would not provide such a navigational search box.
So far, the sites that have been found giving the option are Flickr, YouTube, Metacafe, Amazon, Craiglist, SourceForge and Arsenal.com. It's obvious that there's no way some can compare to the others in number of visits and / or content hosted, so one might wonder what is the algorithm for choosing which sites get the site search box taking into account.
All in all, the newly added feature, although available on a smaller scale at the moment, will be a great boost for the traffic to some of the sites that have notoriously poor search, such as Wikipedia. Being able to google your way through it without having to visit the site itself to perform a search is always an option nice to have.