Sheehan wuchs in einem gemischten, von protestantischen und katholischen Nordiren bewohnten Gebiet an der Springfield Road im Westen Belfasts auf. 1970 wurde seine Familie von Loyalisten bedroht und gewaltsam angegriffen, woraufhin sie in die Falls Road umzog, ein von Katholiken bewohntes Gebiet.
Sheehan trat im Alter von 16 Jahren in die Fianna Éireann, einer republikanischen Jugendorganisation, ein. Mit 19 wurde er erstmals inhaftiert. Ab 1979 wurde er im Maze Prison in den H-Blocks festgehalten, wo er sich am Blanket Protest beteiligte. Nach Angaben von An Phoblacht, der Wochenzeitung von Sinn Fein, war Sheehan im Gefängnis eine ruhige Person und wurde wegen seines Selbstvertrauens von Gefängniswärtern verprügelt.[1] Nach dem Tod von Kieran Doherty trat Sheehan am 10. August 1981 in den Hungerstreik. Er befand sich 55 Tage im Hungerstreik, als dieser am 3. Oktober 1981 abgebrochen wurde. Er hatte danach Probleme mit seinem Augenlicht, war völlig unterernährt und kam in ein Krankenhaus. 1987 wurde er aus der Haft entlassen; 1989 wurde er wegen der Ablage einer Bombe in einem Kontrollpunkt in Belfast zu einer Haftstrafe von 24 Jahren verurteilt.[2]
Im Gefängnis studierte er Philosophie und politische Wissenschaft und schloss mit einem erstklassigen Zeugnis ab; entlassen wurde er nach dem Karfreitagsabkommen von 1998. Sheehan war mit der bekannten Republikanerin Siobhán O’Hanlon verheiratet, einer engen Mitarbeiterin von Gerry Adams, die 2006 starb. Mit ihr hat er einen gemeinsamen Sohn.
