You hit the nail on the head.
Google Analytics is on a substantial proportion of the Internet. 65% of the top 10k sites, 63.9% of the top 100k, and 50.5% of the top million[1]. My own results from a research project I did using the Common Crawl[2] corpus estimates approximately 39.7% of the 535 million pages processed so far have GA on them.
The real key to tracking is the referrer data.
For the vast majority of clicks, you land on a site that has Google Analytics or you've just left one that did.
As Google Analytics tracks your referrer, that means they still have your full browsing history if you jump from GA => !GA => GA => !GA => ...
According to my research[3], Google gets activity information on 51.43% of the 42 billion links analyzed in the 535 million page corpus as either the start or end of the link uses Google Analytics. This activity means they can accurately track browsing history on most sites, even those that don't use GA, simply as timing information, referrers, and knowledge of the web graph end up leaking user activity.
Used in an anonymized fashion, this is beneficial as it helps Google understand real world web traffic and hence rank search results accordingly (far better than simulated activity based upon PageRank or similar).
In the theoretical situation you drop anonymization is where this gets troublesome.
If you're interested, there are more details at "Measuring the impact of Google Analytics"[3], though much of the discussion is on Hadoop + Common Crawl. For a privacy focused write-up (primarily worried about the NSA using Google Analytics), refer to "Google, make Google Analytics HTTPS by default"[4].
P.S. Everyone who notes "Google Analytics is easy to evade" are correct but missing the broader point -- the majority of web users will never do that.
[1]: http://trends.builtwith.com/analytics/Google-Analytics
[2]: http://commoncrawl.org/
[3]: http://smerity.com/cs205_ga/
[4]: http://smerity.com/articles/2013/google_analytics_and_nsa.ht...