Paal was born in Molde, Norway, December 24. 1974, and raised at a jazz club in Stavanger, run by his parents. It was natural to choose his fathers drums as his instrument and jazz as his work. From 1990 on he took actively part in the jazz milieu in Stavanger and joined bands with established musicians such as trumpeter Didrik Ingvaldsen and saxophonist Frode Gjerstad. In many ways, these collaborations were essential as they pointed out the directions for Paal's later musical development and career. During his studies at the Jazz dept at the University in Trondheim, where the first self initiated bands were established, things developed really fast--and Paal was nationally acknowledged at the age of 20.
The forming of the quartet Element in 1993 in many ways represented the start of a new phase in Paal's musical life. Element musically became a platform for several other groups with bassist Flaten and pianist Wiik, and lead to collaborations with Iain Ballamy and Chris Potter, amongst others. Paal moved to Oslo in 1996, where he joined and/or took part in the forming of bands like Vindaloo, SAN, Håkon Kornstad Tio, The Quintet and Frode Gjerstad Trio. He later on got more into self initiated projects and collaborations with Swedish musicians, such as pianist Sten Sandell and saxophonist Mats Gustafsson.
Paal played his first solo concert in 1999, and since then the solo concept has been an important part of his work: Everyone should try doing some solo work, just to feel who you really are and what gets you going. His solo album Sticks and stones was put out in 2001 on SOFA Rec.