EDIT (2019): The below answer predates GDPR and likely requires revision.

Google Analytics has a new set of APIs to assist with compliance with a cookie opt-out. Here’s the documentation, and here’s their help docs.

There has been some ambiguity as to whether the EU Cookie Regulations (as implemented in member countries) require that passive web analytics tracking requires opt-in mechanisms for compliance. If you’re concerned one way or another, consult an attorney. Google is empowering you to make the decision as to how you want to proceed.

They’ll leave implementation details to you, but, the idea is, once you’ve determined whether or not to track the user in Google Analytics, if the answer is to not track, you’d set the following property to true before Google Analytics runs:

window['ga-disable-UA-XXXXXX-Y'] = true;

Where UA-XXXXXX-Y is your account ID in Google Analytics

As the other posters have noted, Google Analytics relies on cookies. So, you’re not able to do any kind of tracking without cookies. If you’ve determined that someone is not to be cookied for tracking, you’ll need to implement something like this:

if(doNotCookie()){
   window['ga-disable-UA-XXXXXX-Y'] = true;
}

Opt In

This does require a little bit of jujitsu for when you first load Google Analytics, since this property will need to be set before Google Analytics runs to prevent tracking from ever happening, which means, for an “opt in to tracking” approach, you’d probably need to implement a mechanism where, on first visit, Google Analytics is automatically disabled in the absence of an opt-in cookie (cookies that determine cookie preferences are explicitly allowed), and then, if an opt-in happens, re-runs Google Analytics. On subsequent pageviews, all would run smoothly.

Could look something like (pseudo-code):

if( hasOptedOut() || hasNotExpressedCookiePreferenceYet() ){ //functions you've defined elsewhere
     window['ga-disable-UA-XXXXXX-Y'] = true;
}
  var _gaq = _gaq || [];
  _gaq.push(['_setAccount', 'UA-XXXXXXX-Y']);
  _gaq.push(['_trackPageview']);


  function onOptIn(){ //have this run when/if they opt-in.
      window['ga-disable-UA-XXXXXX-Y'] = false;
      //...snip...
      //set a cookie to express that the user has opted-in to tracking, for future pageviews
      _gaq.push(['_trackPageview']); // now run the pageview that you 'missed'
   }

Opt Out

With this approach, you’d allow the user to opt-out of tracking, which would mean you’d use a cookie to set the ga-disable-UA-XXXXXX-Y' property and a cookie to manage it in the future:

if( hasOptedOut() ){ // function you've defined elsewhere 
     window['ga-disable-UA-XXXXXX-Y'] = true;
}

  var _gaq = _gaq || [];
  _gaq.push(['_setAccount', 'UA-XXXXXX-Y']);
  _gaq.push(['_trackPageview']);