We have a lot of experience setting up Google Custom Search engines for both CE and EE versions of Magento. Before making the jump to outright purchasing the Google CSE (Custom Search Engine), we recommend installing the free/ad-supported version on a site to see how relevant the results are with the site. Below is a brief, step-by-step overview to setting it up.
1.) Setup your custom Google Search Engine at Google and copy the code they provide.