I don't know if the codecs are installed but "lame" is. It's in /usr/bin. How would I determine if the codecs are installed? Does having "lame" installed indicate that the codecs are installed? Is "lame" the codecs?
On Debian, I install three separate packages: lame, lame-extras, and liblame0. I think the codecs are in liblame0. Can you play mp3 using xmms, or some other player? If you can, you have the codecs.
Grip should work fine with KDE. I'm not familiar with any KDE apps, but sometimes you have to go to the apps preferences screen and help it locate the lame libraries it needs.