I was tinkering around and got the Google API to work on Linux with Mono (tried with Fedora Core 3 and Mono 1.0.4, 1.0.6, and 1.1.6). I thought someone else out there might be interested in doing the same.
1 - Grab the Google Search wsdl file.
wget http://api.google.com/GoogleSearch.wsdl
2 - Use the wsdl utility that is part of mono to generate a C# class that can interact with the Google API web service.
wsdl GoogleSearch.wsdl
This outputs a file GoogleSearchService.cs (here's mine).
3 - Compile the GoogleSearchService.cs class into an assembly.