Getting Zune to recognize it is not hard; it's a registry edit under HKEY_CLASSES_ROOT (HKCR) much like it is on Windows. You can look at how WMA and MP3 are handled.
Adding the codec itself... interesting idea. On desktop Windows, codecs are DLLs (they may have other extensions, but that's what they are internally) that take a compressed stream in one function and return an uncompressed stream. It's relatively easy to add more codec support into the OS; create new DLLs to do the decoding, and register them.
The creation of the codecs is possible. I don't know if managed code would work, so you'd probably need to use the native WinCE dev tools. If there's already a FLAC decoder for older versions of WinMo on AR, it may work unmodified. Registering it, though... no idea how to do that. There may be an API for it, though.
