We've helped lots of customers configure their Salesforce.com integration to Google Apps. From that experience we've learned which Salesforce AppExchange for Google Apps products work well.
Cirrus Insight. You can lookup the relevant Salesforce data as soon as you open an email in Gmail. Plus it's all done in the Cloud so there's no software to install. Just configure it once and everyone in your company can use it.
Contact us if you need help with the set-up or more advanced tricks like only showing the Cirrus Insight Gmail Contextual Gadget to some users instead of all.