What does it mean for an image to be "Markovian"?
It's a probabilistic model that is assumed to generate the image. To make theoretical computations on the performance of certain image processing tasks such as DCT transforming the image for data compression, the image is modelled with a simple mathematical equation.

The Markov image generation model, is used to produce images where there will be high enough correlation between neighbouring samples. This high correlation is therefore efficiently utilized by a transform such as DCT to achieve compression ratios that is close to the maximum available with a nonpractical KLT (Karhunen Loeve Transform) 

As far as I know, it is not much related with markovian fields. 
The simplest 1-D example of such a markov source model, assuming linear dependence between samples, is like: $$x[n] = \rho x[n-1] + {\omega}[n]$$

This simple dependency clearly shows the fact that current sample x[n] is produced from past sample x[n-1] plus a white noise sample w[n], where $\rho$ is the correlating factor and as it is close to 1, samples are highly correlated, when it is close to zero, samples become more noisy and uncorrelated.

For a real image, such a model can only predict samples in a very short duration, because of the non-stationarity of the image. This is one of the reasons why DCT based transforms are applied for short lengths of blocks such as 8x8 pixels.