Several types of cation- and vacancy-ordering are of interest in the LixCoO2 battery cathode material since they can have a profound effect on the battery voltage. We present a first-principles theoretical approach which can be used to calculate both cation- and vacancy-ordering patterns at both zero and finite temperatures. This theory also provides quantum-mechanical predictions (i.e., without the use of any experimental input) of battery voltages of both ordered and disordered LixCoO2/Li cells from the energetics of the Li intercalation reactions. Our calculations allow us to search the entire configurational space to predict the lowest-energy ground-state structures, search for large voltage cathodes, explore metastable low-energy states, and extend our calculations to finite temperatures, thereby searching for order-disorder transitions and states of partial disorder. We present the first prediction of the stable spinel structure LiCo2O4 for the 50% delithiated Li0.5CoO2.