The long-term precise timing of Galactic millisecond pulsars holds great promise for measuring the long-period (months to years) astrophysical gravitational waves. Several gravitational-wave observational programs, called Pulsar Timing Arrays (PTA), are being pursued around the world. Here, we develop a Bayesian algorithm for measuring the stochastic gravitational-wave background (GWB) from the PTA data. Our algorithm has several strengths: (i) it analyses the data without any loss of information; (ii) it trivially removes systematic errors of known functional form, including quadratic pulsar spin-down, annual modulations and jumps due to a change of equipment; (iii) it measures simultaneously both the amplitude and the slope of the GWB spectrum and (iv) it can deal with unevenly sampled data and coloured pulsar noise spectra. We sample the likelihood function using Markov Chain Monte Carlo simulations. We extensively test our approach on mock PTA data sets and find that the algorithm has significant benefits over currently proposed counterparts. We show the importance of characterizing all red noise components in pulsar timing noise by demonstrating that the presence of a red component would significantly hinder the detection of the GWB. Lastly, we explore the dependence of the signal-to-noise ratio on the duration of the experiment, number of monitored pulsars and the magnitude of the pulsar timing noise. These parameter studies will help formulate observing strategies for the PTA experiments.