What licensing issues should I worry about?
Vorbis, Theora, and VP8/WebM are totally free, and not patent encumbered. At least in theory; it's possible that someone will discover patent issues with these codecs at some point in the future. On the plus side, Google has a vested interest in defending Vorbis and VP8 against patent suits, and if anyone can do this, Google can.
AAC is free for distribution. Zencoder takes care of licensing AAC, so you don't have to.
MP3 isn't free - expect to pay 2%-3% of revenue related to MP3 content. See http://mp3licensing.com for more info.
H.264 is sometimes free, and the terms are a little complicated. See this document for details. Basically, if you charge money for H.264 content (either via subscription or on a title-by-title basis), you might have to pay something, depending on volume. But if you distribute H.264 content for free online, there are no required royalties. You might still want to sign some docs with MPEG-LA to get the royalty-free license, though.
As always, consult a lawyer.