The good news is that there's a big gap between people's expectations and what most have already tried.
Cache-clearing and cookie-disabling is a fairly common behavior. But for whatever reason — inconvenience, maybe, or unfamiliarity with the tools — the share of Americans that have tried protecting their privacy in other ways is pretty low.
So what can be done? Here are a few options that don't involve cracking open a computer science textbook.
Encrypt your e-mail. This is by far the scariest-sounding technique, but if you have a set of step-by-step instructions, you'll be up and running in no time. The basic idea is that for every e-mail account you own, you can create a set of public and private keys that will turn your plain-text e-mails into unreadable gibberish.
Encrypt your chats. Instead of using Google Talk or AOL Instant Messenger, try switching to a chat application that supports encryption out-of-the-box. A lot of people on Windows prefer Pidgin (the Mac analogue is called Adium). Illustrated instructions for setting up your first encrypted chat can be found here (Windows) and here (Mac).
Enable incognito mode on your Web broswer. Most browsers come with an private browsing or incognito mode that won't log your search or browsing history and won't retain cookies that sites use to track your behavior. While it won't encrypt the traffic you send over the networks, it's a good way to hide your activity from others who might use the same computer later.
Use a traffic anonymizing service like Tor. Tor routes your traffic through the Web in ways that makes it very hard for someone else to track. When the service is turned on, your Internet traffic looks to outsiders like it's coming from one of Tor's exit relays, which can be located anywhere in the world (read: not where you are). You can download Tor here.
Pay for a private VPN. This option is a lot like using Tor in that your Internet traffic is masked, but depending on your provider, it could come with more features. For the privacy-conscious, TorrentFreak quizzed a number of VPN providers on how they operated their business and only listed those that returned satisfactory answers.
Use a password manager. Part of the point of encrypting your Internet traffic is to reduce the likelihood of someone gaining the passwords to your online accounts. So why not beef up the security of those accounts in the first place? As Microsoft's Troy Hunt writes, the strongest password is the one you can't remember. To help you keep track of them all — and you'll have a lot, if every password is different — use a password manager like LastPass or 1Password. Browser extensions, integration with Dropbox, mobile versions and strong-password generators are all examples of features that help make these tools less of a burden and more useful.