Searching for "Miles Davis" returns 10 pages about Miles Davis. Hitting our engine with Wikipedia data for Miles Davis gives you John Coltrane, Herbie Hancock, Wayne Shorter, Thelonious Monk, Sonny Rollins, Canonball Aderly, and so on.
http://www.directededge.com/?Miles%20Davis
The search end of the spectrum is about finding something you're looking for -- recommendations are about discovering things you didn't know about.
The two meet in the middle with "personalized search". If I type "python" into a search engine, do I want snakes or code? You can probably figure that out based on what I've done in the past.
The difference is in the input data that the search/recommendation engine considers: the input in classic search is only the few words in the query, while a recommendation engine considers some history of your interactions with a site or the internet (and nothing that indicates your intent in this particular instance).
Google, of course, keeps search history for people logged in. But it doesn't seem to affect their relevancy algorithm much, unlike, say, your location and language.
I'd speculate Google Checkout is mostly about gathering data that would allow for meaningful recommendations.
The difference is somewhat arbitrary when you think about it. When I Google, I'm asking it to recommend me stuff related to what I'm looking for. Google is nothing but the world's best recommendation engine.
There are about 1,000 sites that could use good recommendation technology to enhance their profits though, so I like this company's monetization chances. Easy elevator pitch too: recommendations as a service.