Recently a client asked me to make their site "work on smart phones", which normally wouldn't be too much of an issue... However it's a video site, and I have absolutely no idea where to even begin. Right off the bat I'm not even going to consider allowing the site to even function in anything other than Android (Maybe even 2.0+) and iPhone, maybe Blackberry and WinMo. But beyond that... What do I do? I'm looking at using the tag, however I'm unsure what, if any, codecs which phone uses. Is HTML5 even adopted in their browsers yet?

Could someone please point me in the right direction? Am I going about this the right way, using the tag? Or is there some magical html element both iPhone and Android (And BB and WMo) that lets them run video in their native video players (Like on youtube).