FFMPEG library in one form or another is probably the way to go. The VLC Player (videolan.org) makes use of this and supports a huge range of codecs and platforms. The VLC libraries also provide a java wrapper called JVLC which looks like it might do the trick.
Stay tuned... will post more when I have checked things out more.