I know about at least one "sensus plenior" interpretation of the "new song" in Psalm 149, but I have never heard a plausible explanation on what the author intended and how it was understood by his contemporaries.
If we accept that this Psalm was most likely written at the time of the restoration under Ezra and Nehemiah, 'a new song' was probably understood as a new hope of the full restoration of Israel as in the days of David and Solomon.
Israel used various songs everyday to extoll the praises of God, but in remarkable periods of new blessings one should aptly recognize it in a new song, not just a repetition of the same songs that only recognize blessings past. A fresh hope and reason for singing is expressed by the term.
A similar expression is in Psalms 33:3, 40:3 and 92:1 and other places.