It is a cousin of the box weave, which I personally dislike, and therefore have not presented as an instructable. If you do know box weave, however, think of the Byzantine as alternating box weave.
Note! This instructable assumes that you have basic chain working skills.
You may wish to start with Paul the Mole's European 4-in-1 weave instructable to get you familiar with chain working. Euro 4-in-1 is excellent for making sheets of chainmail, and is a great beginner weave. I also have an instructable on making jewelry-size rings, and armor-size rings will be addressed in another instructable.
You will need rings and two pairs of pliers. If you're working with small and soft rings, you can use a ring-tool and a single pair of pliers. I work with tooth-less pliers, as teeth will mark my rings. For many ring sizes, you can use chain, flat, bent or needle nosed pliers, but for some sizes you'll need specific ones. Apply judgment as needed.
Ring size: I frequently use 18ga aluminum wire with 3/16" interior diameter as a good medium ring size. You can go with larger or smaller rings, though the wire-to-ID ratio needs to be within a certain range to produce aesthetically pleasing results. A small wire size with large ID will result in a rather... anemic looking weave, and a thick wire with small ID will be too tight to work with.
See the photo? The IDs are all the same, but the thicker wire looks better. Be careful not to go too thick, though--the weave will get too tight to construct.
If you are interested in additional weaves, let me know (though PMs, emails or comments) on what you want me to demonstrate. If you want an idea of what's out there, take a look at the chainmail gallery on my website.
New and shiny updated video on step 3!