with praise on my lips and a song in my heart

This is a religious cliche- probably from a Pentecostal or Evangelical Christian church.

Praise is referring to praise of Jesus. A song in your heart means keeping a churchy kind of happiness.

The phrase indicates reacting to adversity with religiosity.

"With a song in my heart" is not necessarily, and is not usually, an expression used in a religious context. "With a song in my heart" simply means that one is joyously happy.