Tebbutt is one of seven children. She was born and raised in the country New South Wales town of Forbes. Her family then moved to the Sutherland Shire in Sydney where she attended Our Lady of Fatima Catholic primary school, Our Lady of Mercy College, Burraneer then completed her HSC at De La Salle College, Cronulla. She went on to earn an Economics degree from the University of Sydney, graduating in 1986. She joined the Labor Party in 1985, as a member of its left-wing faction.^[3]

Tebbutt was elected to a seat on Marrickville Council in 1993 before becoming Deputy Mayor in 1995. She was appointed to the New South Wales Legislative Council filling a vacancy following the retirement of Ann Symonds in 1998.^[4]

After the Carr Government was re-elected in 1999, she was Minister for Juvenile Justice. In July 2002, Tebbutt was promoted, given responsibility for the Ministries of Community Services, Ageing, Disability Services, and Youth, whilst retaining the Juvenile Justice portfolio. In a cabinet reshuffle in early 2005, she was promoted to Minister for Education and Training.^[4]

Following Premier Bob Carr's unexpected resignation 27 July 2005, and the resultant resignations of Deputy Premier Andrew Refshauge and Senior Minister Craig Knowles, the 'Triple-M' by-elections for the seats of Maroubra, Marrickville and Macquarie Fields were held on 17 September 2005. The new incoming Premier, Morris Iemma, was said to have favoured her for the position of deputy leader—and hence Deputy Premier—as having a woman in the role would have looked favourably with the electorate. However, in accordance with longstanding Labor tradition, the deputy leader is chosen by the Socialist Left faction.^[5]

Tebbutt resigned from the Legislative Council on 26 August to seek election for the seat of Marrickville. Hence for the three-week period from 26 August to 17 September 2005, Tebbutt was in the unusual, though not unprecedented, position of being a Minister of the State, without being a member of parliament.^[6]

Tebbutt successfully defended the seat of Marrickville for the Labor Party in her by-election. With no Liberal candidate contesting the election in this comfortably safe Labor seat, the ALP primary vote increased, though she suffered a 5.6% two-candidate preferred swing to the Greens.^[7][8]

Tebbutt successfully held the seat of Marrickville at the 2007 election, but announced after it that she would not be a candidate for the new ministry and would return to the back bench so she could spend more time with her family.^[9]

A meeting of the Left faction on 4 September 2008 saw her return to the front bench as she was elected as the Deputy Leader of the NSW Labor Party. Following the resignation of Morris Iemma and the selection of Nathan Rees as the new Premier the following day, she was sworn in as Deputy Premier of New South Wales.^[10] She was sworn in as Minister for Climate Change and the Environment and Minister for Commerce on 7 September 2008.^[11]

A little over a year later, Rees was deposed as Labor leader and Premier, in favour of Kristina Keneally. Tebbutt remained as Deputy Leader and Deputy Premier under Keneally, and became Minister for Health.^[12]

With Labor sinking in the polls going into the 2011 election, there was some speculation that Tebbutt would be toppled by a Green candidate. Indeed, the ABC's Antony Green predicted that Tebbutt would be defeated by Green candidate and Marrickville Council mayor Fiona Byrne. In a very tight contest that came down to less than 680 votes, Tebbutt won the seat with 50.9% of the vote on a two-party-preferred basis, suffering a swing of 8.5%.^[13] The campaign was marked by anti-Zionist protests as four months earlier, Byrne and Marrickvile Council had controversially voted to boycott Israel. There were no allegations that Tebbutt was involved in any of the anti- or pro-Zionist threats that occurred during the campaign.^[14]

In November 2013, Tebbutt announced she was retiring from politics and would not contest the 2015 election.^[15]

After retiring from politics, in 2015 she was appointed as Chief Executive Officer of Medical Deans Australia and New Zealand.^[16] In February 2018 Tebbutt started as CEO of the Mental Health Coordinating Council, the peak body representing the community mental health sector in NSW. In 2023 she became CEO of the not-for-profit Odyssey House NSW, a drug and alcohol recovery organisation.

In 2000, Tebbutt married Anthony Albanese,^[3] later the leader of the Australian Labor Party and 31st prime minister of Australia. Her former state seat of Marrickville was contained almost entirely within Albanese's federal seat of Grayndler, leading the Greens to dub them the "King and Queen of Marrickville".^[17] She and Albanese have a son. They separated in 2019.^[18]