A regression problem amounts to the reconstruction of a multi-dimensional hypersurface from a finite number of noisy samples. In modern engineering regression algorithms play a fundamental role due to their capability of inferring mathematical models of phenomena from experimental measures. Regression problems can be tackled using both parametric and nonparametric techniques. With the latter, overfitting is avoided by penalizing the irregularity of the estimate (Tychonov regularization). Then, the estimator has the structure of a special Neural Network called Regularization Network. These Networks admit also a Bayesian interpretation if the unknown function is modeled as a Gaussian process. Unfortunately, the computational cost of such nonparametric techniques scales with the cube of the number of data. This thesis clarifies several computational and Approximation issues within Bayesian regression theory. In the second chapter (Bayesian regression) an introduction to the basics of Bayesian inference is provided, highlighting the role of Gaussian priors over spaces of functions. The third chapter (State-space methods in Bayesian regression) focuses on mono dimensional regression problems for which the prior admits a state-space representation. In this setting, two new algorithms (with linear complexity) for the computation of the Regularization Network and the so-called equivalent degrees of freedom are presented. In the fourth chapter (Consistent nonparametric identification of NARX models) it is shown that regularization networks are capable of identifying in a consistent way an infinite dimensional class of NARX (Nonlinear AutoRegressive eXogenous) models. Finally, in the last chapter (Finite dimensional models) some procedures for the finite dimensional approximation of the Bayes estimate are considered. New parametric regression algorithms with linear and quadratic complexity are proposed and their generalization properties analyzed. It is also shown how to apply such procedures to the parametric identification of NARX models.