Data others have on you
Of the many places that post or share your information, you usually have an option if you take the time to ask.
Schools, Churches, and Clubs
It's common to put together directories, phone books, or flyers that have the home phone number, address, name, or other important information about you and your family. If asked before-hand, consider not giving them permission. If you were never asked, call and complain. Ask to not be included and that they not use your information without your permission again.
Did you know that the State Department of the United States has an online PDF file that lists the name, organization, location, building, title, and phone number of every single employee? It's 184 pages long full of people who enemies of the government (foreign and domestic) might want to know.
If you were one of those people or if you work for any company that makes it a little too convenient for people with no need to know, talk to your security people, HR, and/or your management. Explain the risks and ask to be excluded (or tell them about this page and let me try to convince them for you).
Some would say that they're public records so they should be online. That's stupid. There is no "American's Only Internet" so what is intended for just the American public is instead dropped into the lap of every dirty thief from around the world.
Putting your personal information online for the entire world to see is an invitation to disaster. If you know someone who thinks that's not a problem, ask them if they've ever heard of something called Identity Theft or Nigerian scams.
Government records must be available to the public without burdensome fees or procedures, but requiring that someone physically come to get them or at least provide proof of identity and a justification for requesting the records is not unreasonable. In fact many states do just that while others are satisfied leaving their citizens completely open to attack.
While there may not be much that you can personally do about your state's document management, you might know someone who is or at least be able to cast votes knowing that this is an issue. Support people and laws who work to maintain your privacy!
Business Profiles of Customers
As you will read in my article about, companies are crazy excited about collecting tons of information about you and reselling it to other companies. Fortunately, many of these companies allow you to restrict or remove your information from their systems. It would be prohibitively difficult for me to list each and every one of the most egregious violators and the steps for removal, but fortunately, I found someone else who has already done it.
Other Websites and Pages
If you find your information listed online, look for an opt-out option or just ask to have it removed. This also counts websites where you might have left a comment or once been a contributing member.
Just remember to ask politely. They're not often obligated to remove your data in any way, but even if they are legally bound, bringing down a legal hammer on people could trigger "The Streisand Effect".
Data under your control
Profiles are things like forum accounts, social site accounts, or anything else that you log into with a name and password. Divide each profile into two simple categories: one you want to keep and ones you don't. For the ones you don't want to keep, rather than deleting them outright, you're better off first "poisoning the well".
Replace any existing data with completely fake information instead. After that you can delete the account and be assured that their last known copy of your data is bogus. For extra points, leave the account active for a few months so the site's regular backups start to store the bogus data in backups as well (thus further making it unlikely that your real data will be restored).
For accounts you want to keep, prune the data as much as possible. Any data that's not strictly required to keep the account functional should be changed or deleted (though changing it to bogus data is better for the reasons I already said). For example, I originally started my Facebook account with my real name, realized that I had no reason to do so and changed my last name to something completely different.