See for example this google query for wikipedia; the first result has both sitelinks and a search box to search within the website.
My site only has sitelinks. Is there anything I can do to make the search box appear?
Webmasters Stack Exchange is a question and answer site for pro webmasters. It only takes a minute to sign up.Sign up to join this community
I think that the search box appears at the discretion of Google and their algorithms, but I have heard that having a CSE set up for your site can increase the likelihood that the box will appear, though this hasn't helped with any of my sites.
This is a little late, but you can now mark up your website with JSON-LD to add a search box below your site links.
When your site will have a PR of 8 or more maybe you will get the search box in Google results too. Just kidding, I think Google placed it there only for Wikipedia, but it's interesting, it might be something experimental and maybe one day Google will place such search box for any site that ranks 1st in a his results.