Hines attended Berkeley Vale Community High School from 1989–1994 and was a regular feature in the school's first XIII rugby league team. He played his club football for the Berkeley Vale Panthers Junior Rugby League Club and was part of the club's first ever Premiership winning side (U/15s – defeated Woy Woy in 1991) playing alongside future NRL player Paul Stringer.
Hines won league and cup titles with Gala RFC, before signing for Edinburgh. He moved from Edinburgh to Perpignan in the 2005 off season.
His time at Perpignan came to an end due to his refusal to play for them in the latter stages of the Top 14 to tour South Africa with the British and Irish Lions. On the Lions tour, Hines played in five regional matches, but was never selected for any of the Tests against South Africa.
Hines made his Test debut for Scotland in New Zealand but two serious injuries claimed nearly 18 months of his career. He became the first Scotland player to be sent off in a Test match when he was dismissed against the USA Eagles in 2002 for punching replacement hooker/flanker Dan Anderson. He was a big part of the Scotland squad for the 2003 Rugby World Cup, which was held in his country of birth.
In the 2005 Six Nations Championship game against Wales at Murrayfield on 13 March, Hines came on in the second half and helped restore some pride, but his try was disallowed for lack of grounding. He was alleged to be discontented with the Scotland coaches (Matt Williams and Willie Anderson) and declared his retirement from international rugby. However, with the firing of the previous coaching regime and the appointment of his previous club coach, Frank Hadden, as Scotland coach, Hines returned to the squad. He made his reappearance as a substitute in the 2006 Six Nations win over England at Murrayfield.
On 9 November 2011 Hines announced his retirement from international rugby with immediate effect. This meant he started and ended his Scotland career at Eden Park, Auckland. Hines won a total of 77 caps and scored two tries (10 points).