Google powers ads just about everywhere on the Web. It's their number one source of income, and Google powers both text ad links and banner ads that appear on all sorts of websites. That may lead to the feeling that Google ads are stalking you. When you visit a site, you may notice ads from a site you've previously visited. When you visit a lot of sites about shoes, you may notice that ads in other sites talk about footwear. That's either very cool and relevant or very creepy, depending on who you ask. Perhaps it's a little of both.
Google does this by using a cookie. It's a small piece of data stored by your browser, and it follows you from site to site with a number that identifies you, or at least identifies a little about you to advertisers. Specifically it identifies a set of interests, previously visited sites, and inferred demographic information. You're not stuck passively accepting this information. You can see and adjust the interest-based advertising from Google by visiting the ads preferences area on Google.
Type http://www.google.com/ads/preferences into your browser. You can also get there by clicking on the "Ads by Google" link on the bottom of ads and then "Ad preferences."
Once there, you can see the categories identified as interests. For instance, one of my interests is identified as, Computers & Electronics - Computer Hardware - Laptops & Notebooks - Tablet PCs. Ok, that's pretty true. I am a lover of consumer electronics. Google also lists my general location, which is certainly relevant to advertising. There's no point in telling me about a sale in New Mexico.
There's also inferred demographic information. Google has decided that I am a male between the age of 35-44. The age is accurate, but the gender not so much. I'm not sure how I'm identified as a man by Google, but I know I'm not the only one of my tech-savvy friends to be misidentified this way.
Changing the Information
You could actually leave things as they are. The only thing this will change is the topics and variety in ads. However, there are some times where it comes in very handy to be able to edit this. You might have visited a few websites out of boredom or curiosity and are now being plagued by ads for cheese graters you don't want. You may be really interested in cameras right now and want to see more ads in the hope someone will post a deal. It may really bother you to see ads targeted toward the wrong gender. You can fix it by clicking the edit or delete button anywhere on the page. You'll be taken to a page where you can remove offending items, add categories (this feels a little like helping someone else do their homework to me) or opt out of personalized ads completely.
If you opt out, you'll still get ads. They just won't be based on interests and inferred demographics from the sites you've previously visited.