Abstract The standard Bayesian technique for searching pulsar timing data for gravitational-wave bursts with memory (BWMs) using Markov Chain Monte Carlo (MCMC) sampling is very computationally expensive to perform. In this paper, we explain the implementation of an efficient Bayesian technique for searching for BWMs. This technique makes use of the fact that the signal model for Earth-term BWMs (BWMs passing over the Earth) is fully factorizable. We estimate that this implementation reduces the computational complexity by a factor of 100. We also demonstrate that this technique gives upper limits consistent with published results using the standard Bayesian technique, and may be used to perform all of the same analyses of BWMs that standard MCMC techniques can perform.