The success of computational materials science in designing the materials of the future relies on the computation of materials properties using temporally expensive computer codes. Surrogate models, or simply surrogates, are employed to approximate the computer code and simultaneously decrease the computational effort by orders of magnitude enabling characterization, optimization, and design of materials in silico. To learn a surrogate, a few observations must be obtained from the expensive code, but once learned, the surrogate can predict the computer code output for any input. In most cases, one is faced with the task of choosing a narrow subset of best candidates among a larger set of potential surrogates for a given task. In this thesis, we present two new methods which improve surrogate modeling, and a third method capable of quantifying the uncertainty in materials properties predicted from the approximating surrogate. Our methods are general, but will be applied to the subset of materials called alloys. We start out by applying information theory to improve thermodynamic characterization of materials using surrogates. We explore employing relative entropy to measure "distance" between Boltzmann distributions, and find that our approach greatly improves current thermodynamic characterization in much better agreement with experiments. Then, we provide a rigorous way to propagate the uncertainty from not know- ing the best surrogate candidate to use and from having observed only a limited number of computer code observations during the process of lining up a set of relevant candidates. We show that the surrogate indeed captures properties to a satisfactory degree, as has been tacitly assumed so far in the field, with a predictive variance on the order of 5-10 %, which can be further improved if needed. Finally, we consider a materials design problem using surrogates. We consider the task of minimizing the thermal conductivity in nanowires. The low symmetry of these wires motivates us to introduce a modification to the traditional surrogate model employed to learn the property of such systems. We call the new technique the cluster expansion ghost lattice method and show how the method successfully predicts the nanowire structure with lowest thermal conductivity.