Gaussian processes are powerful Bayesian non-parametric models used for their closed-form posterior and marginal likelihoods. Yet, traditional methods for computing these quantities are not scalable to large data sets. And traditional kernels often do not express inductive biases that allow sample-efficient learning. Finding and exploiting structure in Gaussian processes builds a path towards tackling both problems. However, this has traditionally been accomplished through burdensome learning procedures, often by maximizing the marginal likelihood or variational objectives. In this thesis, we present methods for creating and exploiting structure in Gaussian processes directly. We first present randomly projected additive Gaussian processes, a class of Gaussian processes whose kernels operate additively over a set of random data projections. We prove that these kernels converge almost surely to a limiting kernel, which can be analytically derived in certain cases. We derive error bounds that characterize this convergence rate. We propose modifications to randomly projected additive Gaussian processes that improve their empirical convergence rate and regression performance. Next, we present algorithms for performing efficient online Gaussian process inference. Specifically, we present algorithms for computing the marginal likelihood, score function, and predictive distributions in constant time with respect to the number of observed data by using kernel interpolation approximations and algebraic manipulations using the Woodbury matrix identity.