The Byzantines went into the dark ages with some major advantages, which is why they could be considered for most of their history to be one of the main players on the world stage- and one of these advantages was that they inherited the Late Roman military, which for all its faults, was still vastly superior to anything the rest of the world had at the time- at least, when you had a stable economic system to actually fund it, as the Western Roman empire found out the hard way.
The basic set up of the Byzantine empires military was that of the late Roman empire- local lords appointed by the emperor would rule over a swath of land they often owned portions of, and act as the local governor and military commander for provincial troops- these troops would be used to harass, and slow enemy forces by use of guerilla tactics and skirmishes until the main Imperial army arrived to do battle. The primary changes to this set up were more in how this system was supported, rather then a change in how it was implemented, and the creation of the thematic system- a very important development for the Byzantine empire, was important because it made the traditional system more reliable, and easier to implement- but more then anything, it was more easy to support financially.
For most of the history of Byzantine empire, the elite of the elite in terms of troops was the heavy cavalryman known as the Cataphract. The Roman Cataphract that was inherited by the Byzantines was a fearsome sight- heavily armed and armored trained to use lance, sword, mace and bow, these heavy cavalry had their origins in the army of Roman Emperor Trajan, and had gradually increased in their usage thought Roman history, eventually superceding the infantry by the 4th century in importance and tactical usage. Though it would take it the last eastern Romans to refine the Roman cataphract to include archery among his skills, by taking example from the huns- further refinement on these troops was had during the Byzantine period directly.
The Byzantine empire otherwise specialized their soldiers in differing groups, as the Romans had before them, including light cavalry, Heavy Infantry, light Infantry- and mercenaries. While unlike western Rome, Eastern Rome had never turned to mercenaries to be the mainstay of its field armies (by the end, only around 5-7 out of every 10 troops was of Roman origin in the west; though that same number was probably also had by the Ostrogoths in their own armies before the eastern Romans claimed Italy) But the use of mercenaries as further speciality troops was well established- by the Byzantine empires end it too, like western Rome would have huge portions of its field army made up by Mercenaries, some forced by the loss of Anatolia. (many theories predominate about why it was never reclaimed, including that doing so would have given local lords too much power over the emperor) The mercenaries were often grouped by their home region- units such as Latins (Italians, and Occitanians), Inglinvarrangoi (English Saxons forced out by the Normans), Massagetoi (Christian Turks, among other steppe peoples) - and many, many others- but the most famous of these Mercenary forces, would be the well known Varangian Guard- made up of Scandinavians and Russians (though most often Russian Scandinavians)- the Varangians being known for their loyalty to the emperor, and eventually becoming his personal body guards (because of their loyalty to the emperor, and general unpopularity with the people made the Varangians have to stay loyal to the emperor, so that they might not be kicked out of the city) The Varangians proved themselves in 1203 when the all of the other mercenary contingents refused to fight for lack of pay- however, despite this, the Varagnians seemed to have never recovered from the essential death blow this was, and they are no longer recorded as contingent of any status after 1204, though other Mercenaries such as The Latins and Massagetoi among others continued to be service.
Overall, the Byzantine army can be split into two periods- there are more divisions possible mind, including some major one, but for the novice this is all one needs- pre Manzikert is essentially the Thematic army evolved from the late Roman system, post Manzikert is the increased use of Mercenary regiments in the empire