Johnsen begon zijn voetbalcarrière bij Skotfoss IL. Hij maakte zijn debuut in de Tippeligaen, de Noorse eerste klasse, bij Odd Grenland in 1999, op 25-jarige leeftijd. In 2000 ging hij naar Rosenborg, waar hij John Carew moest vervangen. Ondanks de interesse van RCD Mallorca en Sparta Praag in 2005 bleef Johnsen tot 2006 bij Rosenborg.
In zijn periode bij Rosenborg werd hij tweemaal topschutter van de Tippeligaen, in 2001 (met 17 goals) en in 2004 (met 19 goals). In juli 2006 tekende hij een contract voor achttien maanden bij Nagoya Grampus Eight. Bij zijn debuut in de J-League, op 29 juli 2006, scoorde hij twee keer tegen JEF United.
Johnsen speelde 33 interlands in de periode 2000-2007 en hij scoorde daarin tien keer gedurende die periode voor de Noorse nationale ploeg. Hij maakte zijn debuut op woensdag 16 augustus2000 in de vriendschappelijke uitwedstrijd tegen Finland (3-1), toen hij na 71 minuten inviel voor Steffen Iversen. In 2013 keerde hij terug in de nationale ploeg en speelde op 39-jarige leeftijd nog twee interlands voor zijn vaderland. In de laatste van die twee duels, op 15 oktober2013 tegen IJsland (1-1), was hij 39 jaar, 6 maanden en 28 dagen, waarmee hij de oudste speler ooit werd van de Noorse nationale ploeg[1]
Zuid-Korea – Noorwegen 
36'
.svg){kind=small}
Honduras – Noorwegen 
Estland – Noorwegen 
Rosenborg BK
Péter Kovács & Zdenek Ondrasek (14 goals) (2012)
Vidar Örn Kjartansson (25 goals) (2014)