Intuitive explanation of a stochastic PDE Lindgren et al 2011 connects Gaussian Markov Random Fields (which have fast calculation properties due to the Markov attribute) and Gaussian Processes (which can model many types of data). The connection rests upon the fact (from Whittle 1954) that solutions to a certain stochastic partial differential equation (SPDE) defined below have a Matérn covariance (common in Gaussian Processes). 
They then show that some models with defined Markov properties (like on a lattice, but they extend it to off-lattice data) are solutions to that SPDE and so all the fast calculations (such as the precision matrix) that can be done on Markov models lead to desired covariance properties. So we can do some GP calculations very quickly with this technique. 
My questions are about the SPDE itself:
$$
(\kappa^2 - \Delta)^{\alpha/2}x(\mathbf{u}) = \mathcal{W}(\mathbf{u})
$$
where $\Delta = \sum \frac{\delta^2}{\delta x_i^2}$ is the Laplacian,  $\mathcal{W}$ is a white-noise process, $\alpha/2$ is an integer, and $\kappa$ is a constant that represents the inverse "range" of the covariance (something like a persistence length). What does this very weird equation represent? I hate to pull an "I don't get it" so here are some specific questions:


*

*On the LHS we have the Laplacian operator, which is the divergence of the gradient. What does a PDE with this operator imply about the solution? E.g. "$dx/dt = a$ means that x changes with speed $a$."

*On the RHS we have a stochastic white noise process $\mathcal{W}$. How is this different from putting something deterministic here? In the paper they call this "driving the SPDE with white noise" but I don't know what driving means in this context.

*They mention in the paper the relationship of this equation to diffusion. It would be helpful to flesh out that connection.

*They further extend this model to non-stationary fields with a slightly modified SPDE:
$$
(\kappa^2(\mathbf{u}) - \Delta)^{\alpha/2}\left\{\tau(\mathbf{u})x(\mathbf{u})\right\} = \mathcal{W}(\mathbf{u})
$$
Where functions $\kappa^2(\mathbf{u})$ and $\tau(\mathbf{u})$ vary throughout space. They show this ALSO has "local" Matérn covariance but globally could be a dense covariance with interesting global correlations. How does this relate to the intuitive picture from the simpler equation?
 A: Ultimately, this is a very broad question so I won't even attempt to answer it completely. Stochastic PDEs are entire area of active research. Your confusion basically boils down to "what are SPDEs" which people spend careers answering.
Let me briefly remark on a few points:

On the LHS we have the Laplacian operator, which is the divergence of the gradient. What does a PDE with this operator imply about the solution? 

If you have studied (non stochastic) PDEs you should have studied the Laplace equation, $\Delta u =0$, or with driving force $\Delta u = f$. I couldn't write up a full treatment of Laplace's equation so I won't. In most SPDEs there is a time component so there are the heat equation, $\frac{\partial u}{\partial t} =\alpha \Delta u$, and Schrödinger equation, $\frac{\partial u}{\partial t} = (i\alpha \Delta +V)u$. I can't go through a full treatment of these, either.
What you have is not exactly the Laplacian operator. You have a generalization called the fractional Laplacian operator. We define this operator by its Fourier transform. Recall: $\mathcal{F}(\Delta u )(\textbf{k})=\|\textbf{k}\|^2\mathcal{F}(u)(\textbf{k})$. So the so called "fractional Laplacian operator" has the following property: $\mathcal{F}(\Delta^{\alpha/2} u )(\textbf{k})=\|\textbf{k}\|^{\alpha}\mathcal{F}(u)(\textbf{k})$. See their definition of $(\kappa^2-\Delta)^{\alpha/2}$ here, which should not be that surprising.

On the RHS we have a stochastic white noise process W. How is this different from putting something deterministic here? In the paper they call this "driving the SPDE with white noise" but I don't know what driving means in this context.

At the heart of SPDEs is that noise term, that is the object of study. $\mathcal{W}$ is a distribution, meaning it is an object like a Dirac $\delta$ "function". It is a Gaussian distributed random field. Defining this object rigorously is not trivial. Like the Dirac $\delta$, it only makes sense when paired with nice functions (this is the integral formulation I was telling you about in the comments. This is very important). I recommend this paper by Davar Khoshnevisan, pages 1-4 (including equation 2.1) for a fairly complete definition of this process in the case of the stochastic heat equation which should give some insight. Also see this question for more information on the $\delta$ "function".
Here is a video of Field's medalist Martin Hairer explaining to a layman what and why we should study stochastic PDEs (this video is absolutely painless, no real math). This should answer your questions.

They mention in the paper the relationship of this equation to diffusion. It would be helpful to flesh out that connection.

I actually did my undergrad thesis on this connection. Basically, the (non stochastic) heat equation can be derived and solved entirely in terms of Brownian motion. Einstein did this in 1905, from a macroscopic level and Smulochowski did this from a microscopic level. I go over both derivations in my thesis. You can solve the heat equation in terms of expectation of Brownian motion. This is called the Feynman Kac formula. If you do Wick rotation to imaginary time, you get the solution to the Schrödinger equation. The solution to the Schrödinger equation is given by Brownian motion running in imaginary time. This is known as Feynman path integration, and was the subject of his PhD dissertation. 
See also a post I answered on MO for this connection. 

How does this relate to the intuitive picture from the simpler equation?

I'm not sure, I haven't read their paper, sorry. :)
SPDEs are a beautiful and useful field, I am glad you came across it. It is, however quite technical. I recommend a few mathematician's papers. I recommend: 
Samy Tindel
Carl Mueller
Davar Khoshnevisan
I want to remark on one last thing. The field of SPDEs was recently changed by Martin Hairer's work on rough path theory and regularity structures, for which he received the Field's medal in 2014. I asked a question about this when I first joined math.SE, you can see here. I have since learned a great deal about rough path theory. You can see Martin Hairer's papers here, but be forewarned that they are extremely advanced.
I'm not sure if I answered any of your questions satisfactorily, but I hope I at least gave you some material to look for the answers. I am glad you are interested in this field! 
If this is too much information, just watch the video from Martin Hairer. It is painless. 
