Yes, Google "spies" on us. But that's explicit; it is written in the usage conditions. If you go to www.google.com
and click on the "Privacy & Terms" link, you can get to a page linking to their Privacy Policy and their Terms of Service (these documents are the ones for Canada, different versions may be applicable depending on your country). Google made quite some effort to write these documents in clear human language rather than arcane legalese, but they still are quite long, so allow me to summarize them:
By using Google's services, you allow them to collect information on you, and use it for several purposes, main of which being targeted advertising. The information they collect includes your search queries, the contents of your Gmail emails, your OS and browser versions, your behavioural patterns...
I suggest that people interested in the subject make the effort of reading both documents extensively; they are instructive.
Is it legal ? Given that there are 193 sovereign countries in the World, and that some (actually many) of them are federal states whose individual provinces or regions often exercise some considerable legislative autonomy, then there are hundreds of jurisdictions to take into account, and any precise answer to that question would be much longer that even I would care to write.
Google is rich enough to buy extensive legal consulting, so chances are that what they do is legal, or at least was made legal. There can still be local variations. For instance, in France, handling of personal information is regulated by the CNIL which is currently battling with Google on these matters. So while what Google does is, on average, built on sturdy legal foundations, the jury is still out in many jurisdictions.
What is the big picture ? An important point to be made is that there are consequences. A rather common but simplistic reflex is to declare that one party is Evil and the other is Good, and be done with it; this is how most Hollywood action movies work, and this manichaeism now permeates the way the "general public" envisions political issues which exceed in scope and scale what can be dealt with within the boundaries of a small village. It would be easy to simply state that "Google is evil, they are villains, let's kick their ass." The reality is somewhat more complex.
Indeed, Google offers services which many people have come to consider as essential. I have known the Internet before the search engines, and it was rather hard to navigate. However, servers and code don't grow on trees; to have a service which works as well as Google's, be it a search engine, a video hosting platform or a reliable Webmail, some resources must be used at some point. To speak crudely, this costs money. Quite a lot of the stuff, actually.
Google is a private venture which aims at making more money than what it began with, and it is apparently quite successful at it. From the Wikipedia page, we can learn that Google makes more than 50 billions of dollars per year, and 96% of it comes from ads. This "spying" is their life force. Google can provide their nifty services to us, for free (apparently), because they can gather some personal information from users and use it as fuel for their advertisement business.
We are paying for the Internet with our privacy. That's the naked truth of it. That which we pay to Internet Service Providers, and indirectly through our taxes and subsequent state investments into infrastructures (direct or through subventions), would not be sufficient to pay for the Internet as we experience it today. It would allow for the copper cables and optic fibres, but not for all the data organizing that Google and its ilk provide (all that I say would also apply to Yahoo!, Bing, and all others, but Google is the pack leader so we can concentrate on them for now).
Google's services are paid for by advertisers, who in turn feed themselves, through Google, on our privacy. That's the deal which is in place. Right now.
Does it bother me ? Not the concept. My privacy is mine, so it is mine to give or sell. As @tylerl explains, this has side benefits, in that targeted ads are just that: targeted. What bothers me is that:
The whole deal is global in nature; either everybody sells their privacy to pay for the Internet, or not. There is little room for individual choices. I cannot really decide whether I, personally, will yield to Google's prying eyes or not. This is as if my privacy had become part of a general "shared privacy" (however weird this sounds) which has to be managed as a shared resource, like air, water or oil. History shows that my fellow humans are not very good at making adequate management of shared resources.
Most people don't realize that they get a cheap Internet because of such deals. They believe that once they have given their monthly 30 EUR to their ISP, they are done with it and can download and surf and be entertained without any limit. They don't understand how implausible such a deal would be.
If we are paying for the Internet with our privacy, then I have the nagging feeling that we are selling very cheap. Google makes a lot of profits; this may indicate that the services we get from Google are actually worth much less than what our collective privacy was.
My current plan is to raise awareness and understanding of these issues, as in the present text. The more people think about them, the more probable it becomes that someday, someone will come up with something intelligent to say on that subject.