As seen on the halo.bungie.org forum:

Matt Soell informs us that:

The trailer will first appear on the cover CD of a major PC gaming magazine. It will be their August issue, which hits the streets mid-July.

Shortly thereafter it will appear on the Bungie web site (or more likely, the Bungie site will link to some other site with incredible bandwidth where the files will be hosted) for free download. The movie, I am told, will be roughly 100 megs compressed, so this is quite a time investment for those of you without DSL or cable.

The fabled DVD version may happen if we can find a place that can replicate them cheaply, but so far this has not happened.

Check out the thread!