Magnetic field-based localization is a finger-printing technique using position-dependent distortions of the Earth magnetic field that enables localization in GNSS-denied areas like indoor environments. In addition, magnetic localization is passive and does not require dedicated devices in the infrastructure as it would be the case for comparable RF-based techniques. In this paper, we show how to analyze the achievable position accuracy of magnetic localization based on Bayesian Cramer-Rao lower bounds. The derivation of the bound requires an analytical model, e.g., a map or database, that links the position that is to be estimated to the corresponding magnetic field value. Unfortunately, finding an analytical model from the laws of physics in not feasible due to the complexity of the involved differential equations and the required knowledge about the environment. In this paper, we therefore use a Gaussian process (GP) that approximates the true analytical model based on training data. The GP ensures a smooth, differentiable likelihood and allows a strict Bayesian treatment of the estimation problem. Based on measurements in an indoor environment, the bound is evaluated for different sensor heights and is compared to the mean squared error of a particle filter. Furthermore, the bound is calculated for the case when only the magnetic magnitude is used for positioning and the case when the whole vector field is considered. For both cases, the resulting position bound is below 10 cm indicating an high potential accuracy of magnetic localization.