The same way all the other apps do it. Create hooks, but don't distribute any actual codecs. You then leave it up to the user to purchase or "purchase" codecs. You are legally in the clear, it makes your job a lot easier, and it means that your app is less bloated.

To take one example, it is technically illegal to encode mp3 files using LAME(hence the name, LAME Aint an MP3 Encoder). Apps like Foobar2000 on windows get around this issue by simply not distributing LAME.exe(or any other codec) and then asking you to point to it before you do a conversion. This also has the added bonus of allowing users to use the most current codecs immediately upon release instead of having to wait for another revision of their application to incorporate them.

Also check this out:

http://fedoraproject.org/wiki/Interviews/CodecBuddy