The UK and some other European countries have pushed through legislation in the EU which requires ISPs and phone operators to retain traffic data - information about your net and phone use.
The Regulation of Investigatory Powers Act 2000, which allowed investigative authorities including the police, MI5, MI6, GCHQ, and even local government authorities the power to order communications service providers (CSPs) to retain all communications data on a specific individual under suspicion. However, this was limited by the fact that the CSPs would only retain data beyond their usual requirements (for billing usage - less than 6 months) after the order was given, so law enforcement argued that plots already underway were difficult to investigate given that prior data had not been retained.
The Anti-terrorism, Crime and Security Act 2001 was rushed through parliament following the 9/11 bombings in the United States, and that covered, among a wider range of other issues, data retention. Parliament passed a voluntary code in 2003 that allowed CSPs to judge whether a case was proportional or not, and give information only when deemed appropriate by their judgment. Law enforcement agencies claimed that this still wasn't enough, as CSPs were worried about implications in light of Article 8 of the European Convention on Human Rights, and since cooperation was voluntary they were worried that the CSPs would not cooperate(Though significant cases where this actually happened are non-existent).
This is the most recent legislation, so now, in accordance with the Data Retention Directive, CSPs are required to retain these categories of data(listed in Article 5 of the Directive).
Recent moves in the UK would go above and beyond EU Law by retaining third party data whereby communications made through websites such as GMail and Facebook would be monitored (still the traffic data, not the content). This legislation has not been passed but the government appears to have been trying to get it through parliament for the best part of the last 5 years.
Data Retention is mandated by the EU Data Retention Directive, now active in law.
ORG has also managed to get press coverage of this issue.
Other Relevant Links
Oh, and the Home Office sent a piece from Minister Hazel Blears about "Why data retention is such a good idea" to ORG Board member William Heath for the Ideal Government blog. Read it and comment here.
In July 2012, the Attorney General’s Office in Australia published a discussion paper entitled “Equipping Australia Against Emerging and Evolving Threats”. The discussion paper gives power to 16 state and federal security agencies to monitor private communications, including those of Facebook and Twitter. The main provision of contention is found on page 13 of the discussion paper, outlining that government aims involve:
Modernising the Industry assistance framework Establishing an offence for failure to assist in the decryption of communications Instituting industry response timelines and tailored data retention periods for up to 2 years for parts of a data set, with specific timeframes taking into account agency priorities, and privacy and cost impacts 
A committee is currently reviewing the proposals and so there will be no action until they reach a decision and the Attorney general recently responded to criticism of the proposals by saying:
"We don't want it to be a free-for-all for governments or police to be able to trawl through everything people are doing on the internet. And I think people have misunderstood the proposal. It's very much a targeted approach to make sure that we don't lose important information for investigations."
The EFA, (Electronic Frontiers Australia) countered such views, providing persuasive arguments to counter the discussion paper. One main contention is the sheer cost of storing data.
As you increase the amount of data retained, the period of time for which it is retained and the number of organisations required to retain it, you are inevitably significantly increasing not only the costs in the most literal sense of financial costs and so forth but also the degree to which society and the culture of our society is turned towards one in which there is a climate of fear and a climate of concern about being surveilled by the government and a lack of respect for the government and the rule of law, and those are all very serious civil liberties issues which are very difficult to effectively address. 
Storing every Australian citizen’s data for a period of 2 years will mean that costs to store will be high. The EFA also question whether the data will be safe because the only manner of storing will require:
That you keep sensitive data encrypted normally when not actually in use. If you keep it backed up or on a CD for transport or any of those kinds of things, the backed-up form or transport form of that data, where it is not in active use, should be encrypted. In the event that it falls into the wrong hands or is lost in the mail or whatever—and these things do happen: laptops get stolen or lost on trains and planes—you would hope that that information is encrypted so that it cannot be used by the first person to pick it up. 
The EFA believe that the technologically savvy can avoid the measures, meaning that a great deal of relevant information is not stored. this in turn means that the majority of information is largely irrelevant and harmless data, which in turn means that the measures do not appear to some, to be cost effective.
- 2009-04-06 - OUT-LAW - Internet data to be stored from today
- Summary: Internet service providers will have to store details of web and email traffic and details of internet phone calls for 12 months from today as expanded European legislation comes into effect. The European Parliament passed the Data Retention Directive in 2006 in response to terrorist bombings in London in 2005. It required phone companies to store records of where and when phone calls were made. Those rules have now been expanded to include logs of internet communications.
- 2009-04-06 - BBC - Net firms start storing user data
- Summary: Details of user e-mails and net phone calls will be stored by internet service providers (ISPs) from Monday under an EU directive.
- 2009-04-06 - ZDNet - Internet data-retention law comes into force
- Author: Tom Espiner
- Summary: Internet service providers will have to retain details of internet communications, including email, under UK law which came into force on Monday. The Data Retention (EC Directive) Regulations 2009 require service providers to retain details of user internet access, email and internet telephony for 12 months. ISPs must also be able to respond to access requests by law enforcement and other designated authorities.
- 2009-01-10 - Belfast Telegraph - Call for safeguards over Big Brother database
- Author: Robert Verkaik
- Summary: Plans for a Big Brother database holding records of every citizen's emails, internet visits and mobile phonecalls must include proper safeguards to protect the public from abuses of privacy, the head of the Crown Prosecution Service has warned. Keir Starmer QC, the Director of Public Prosecutions, speaking publicly for the first time since taking up his post in November, said the Government, police and security agencies should only be allowed to collect and use that data where there was a clear "legitimate purpose" that justified the invasion of an individual's privacy.
- 2009-01-10 - The Independent - Call for safeguards over Big Brother database
- Author: Robert Verkaik
- Summary: Plans for a Big Brother database holding records of every citizen's emails, internet visits and mobile phonecalls must include proper safeguards to protect the public from abuses of privacy, the head of the Crown Prosecution Service has warned. Keir Starmer QC, the Director of Public Prosecutions, speaking publicly for the first time since taking up his post in November, said the Government, police and security agencies should only be allowed to collect and use that data where there was a clear "legitimate purpose" that justified the invasion of an individual's privacy. ... Mr Starmer said: "By its very nature criminal investigation touches on privacy. I think the right balance for any investigation or prosecution has got to have a legitimate purpose. Investigation of crime is a legitimate purpose." But Mr Starmer stressed, there must also be "effective safeguards" to act as a break on the state's invasion of the public's privacy. His predecessor, Sir Ken Macdonald, described the database as an "unimaginable hell-house of personal private information" while the Government's independent reviewer of terrorism, Lord Carlile QC, attacked the raw plans as "awful". ... A Home Office spokesman said: "Communications data is crucial for the police to be able to investigate and identify criminal suspects ... in increasingly complex criminal and terrorist investigations and will enhance our national security."
- 2009-01-09 - The Guardian - Superdatabase tracking all calls and emails legitimate, says DPP
- Author: Afua Hirsch
- Summary: Controversial plans for a "superdatabase" tracking all phone and internet communications today received the tacit support of the new director of public prosecutions (DPP). In his first public briefing since taking over as DPP in November last year, Keir Starmer QC said the plans were legitimate, provided certain safeguards were in place. "There has always been a tension between the retention of private information necessary for the investigation of crime and privacy," Starmer said. "Any invasion of privacy will have to have a clearly defined purpose, be necessary and proportionate, and have effective safeguards. If those features are in place it is obviously legitimate to collect data."
- 2009-01-09 - The Register - Confusion reigns ahead of comms uberdatabase debate
- Author: Chris Williams
- Summary: Disentangling IMP from the EU Data Retention Directive. Jacqui Smith will soon begin one of the Home Office's famed consultation exercises on new systems demanded by spy chiefs to snoop on internet communications in the UK. But already, the mangle of powers and regulations around data retention threatens public understanding of what is being suggested.A somewhat confused report from the BBC today attempts to trace the links between the Interception Modernisation Programme (IMP) and the imminently-in-force EU Data Retention Directive (EUDRD) ...
- 2009-01-09 - BBC - UK e-mail law 'attack on rights'
- Summary: Rules forcing internet companies to keep details of every e-mail sent in the UK are a waste of money and an attack on civil liberties, say critics. From March all Internet Service Providers (ISPs) will by law have to keep information about every e-mail sent or received in the UK for a year. Human rights group Liberty says it is worried what will happen next.
- 2007-06-14 - The Register - Data retention laws do not cover Google searches
- Summary: Google is not bound by the Data Retention Directive when it comes to search engine logs, Europe's data protection committee has said. Google has used the Directive to justify keeping data, but OUT-LAW has learned that the law does not apply.
- 2007-04-05 - Computing - ISPs uneasy about data retention
- Author: Tom Young
- Summary: ISPs are concerned about plans to make it a legal requirement to store and provide data about communications to police and security services on request ... New laws could conflict with Data Protection Act
- 2007-04-03 - OUT-LAW - Home Office publishes data retention proposal
- Summary: The Home Office has published draft Regulations to require the retention of certain call data by phone companies for 12 months. Internet telephony and internet access data will not be covered for the time being.
- 2006-08-12 - The New York Times - Your Life as an Open Book
- Author: Tom Zeller
- Summary: ... In December, the European Parliament passed sweeping data retention rules aimed at the telecommunications and Internet industries, requiring that fixed-line and cellphone records, e-mail and Internet logs be stored for up to two years. The measure was lauded by law enforcement groups but decried by privacy advocates and even industry, which would have to find space — and money — to store it all. ...
- 2006-08-24 - Heise - Federal Ministry of Justice to stick with its plans for telecommunications data retention
- Author: Robert W. Smith
- Summary: Despite profound doubts having been raised about the implementability into German law of the controversial EU directive on the retention of telephone and Internet data the German Federal Ministry of Justice is continuing to work on a draft bill to this effect. ... An expert opinion expressed serious doubts about the implementability into German law of the requirements set out by Brussels, especially with regard to the fact that Germany's Basic Law constitutionally guarantees the Federal Republic's citizens the right to informational self-determination.
- 2006-08-17 - Heise - New doubts about the legality of telecommunications data retention
- Author: Stefan Krempl and Robert W. Smith
- Summary: In an expert opinion the Scientific Services of the lower chamber of Germany's federal parliament, the Bundestag, have voiced serious doubts about the implementability into German national law of the controversial EU directive on the retention of telephone and Internet data. "There are serious doubts about whether the directive in the form adopted is compatible with the law of the European Communities,"
- 2006-08-10 - Silicon Republic - The spies who came in from the cold
- Author: John Kennedy
- Quote: Referring to the EU Data Retention Directive, McIntyre adds: "There is nothing to stop information from being sold and I’m almost certain that it could happen. This extends to corporate espionage. The European Parliament has actually accused US firms of being engaged in industrial espionage against European firms and I think storing large quantities of sensitive data creates an irresistible target."
- 2006-07-10 - Silicon Republic - Insufficient challenge to state-sponsored spying
- Author: John Kennedy
- Summary: A challenge filed by the Irish Government to the EU’s Data Retention last week does not take account of privacy concerns of Irish citizens, a lobby group has claimed. Privacy advocacy group Digital Rights Ireland (DRI) said the challenge will delay implementation of the contentious directive — which requires telcos and internet service providers to retain data for a number of years at the discretion of each respective EU state — and stands a good chance of striking it down in its entirety.
- 2006-01-12 - Silicon Republic - Big brother is watching you
- Author: John Kennedy
- Summary: The contentious EU Data Directive that gives each member state the powers to store all phone, SMS, internet, fax and email data for a minimum of six months was voted in last month by 378 MEPs, with 197 voting against. The directive has been deployed as a means to protect European citizens against terrorism and crime, but various industry and civil rights groups argue that not only does this infringe on privacy rights but it makes the assumption that citizens are already guilty.
- 2005-12-7 - The Register - MEPs urged to reject data retention plan
- Author: OUT-LAW.com
- Summary: "Privacy International and European Digital Rights (EDRi) are calling on MEPs to reject a proposed Directive on data retention when it comes before the European Parliament next week following an agreement reached by EU Ministers on Friday."
- 2006-05-12 - EU Observer - US could access EU data retention information
- Author: Helena Spongenberg
- Summary: US authorities can get access to EU citizens' data on phone calls, SMS messages, and emails, giving a recent EU data-retention law much wider-reaching consequences than first expected.