Speech Compression - In LPC how does the linear predictive filter work on a general level?
LPC voice coders (starting with the old LPC10 standard, which seems to be the one you refer to here) are based on the source-filter model of speech production. Speech can be characterized by the following properties:


The raw sound emitted by the larynx (through vibration of the vocal folds, or just air flowing through it, the vocal folds being opened).
The transfer function of the filter achieved by the articulatory system, further filtering this raw sound.


Early LPC coders (LPC10) adopt the following model of those two steps:


The larynx emits either white noise, characterized by an amplitude $\sigma$ ; or a periodic impulsion train, characterized by an amplitude $\sigma$ and a frequency $f_0$
The transfer function of the articulatory system is of the form $\frac{1}{1 - \sum_k a_k z^{-k}}$, and is thus entirely characterized by the coefficients $a_k$


The principle of early LPC coders (such as LPC10) is thus to estimate these parameters from chunks of the incoming audio signal ; transmit these over the network ; and have a sound generator reproduce a sound from these parameters on the receiver. Observe that in this process, nothing of the original audio samples is actually transmitted. To make a musical analogy, it's like listening to a piano performance, transcribing it, sending over the score, and getting someone to play it on the other end... The result on the other end will be close to the original performance, but only a representation has been sent over.


  does this mean that we keep a running average of last p samples at
  both the encoder and decoder?


No, this is not how it works. On the encoder side, we run a process known as AR (autoregressive) estimation, to estimate the set of coefficients of the AR filter that matches best the spectral envelope of the input signal. This is an attempt at recovering the coefficients of the filtering that has been performed by the articulatory system.

These coefficients are sent over the network (along with pitch, the voice/unvoiced flag, and loudness). The decoder uses those coefficients to filter a synthetic excitation signal, which can be either white noise (unvoiced frame) or a comb of periodic impulsions (voiced frame). These coefficients are used in the following way on the decoder to recover the output signal $y(n)$:

$$y(n) = excitation(n) - \sum_k a_k y(n - k)$$

Observe that since this is an all-pole, IIR filter, the samples linearly combined are previous samples produced by the filter.


  So that at the encoder we only transmit
  data that corresponds to the difference between this average and
  actual signal?


There is no "averaging" and there is no transmission of a difference signal. The decoder is a sound synthesizer with some parameters ; and the encoder searches for the set of parameters for this synthesizer that most closely matches the input signal.


  Why is it an a linear combination of these previous samples?


Other options would be possible indeed here, but the advantage of using an auto-regressive model are the following:


In this model we use an all-pole IIR filter to simulate the articulatory system. This is a good model, since it can capture strong spectral dips and peaks with a small number of coefficients ; and the articulatory system is indeed capable of emphasizing / attenuating narrow bands of frequencies (See formants). If we had used an all-zeros FIR filter, we would have needed many more coefficients to accurately capture the kind of filter responses that the articulatory system can achieve.
On the encoder end, the problem of of estimating the filter coefficients is computationally efficient - it can be done using the Levinson-Durbin recursion on the first few samples of the autocorrelation. More complex linear models (ARMA) or non-linear models are more computationally expensive or intractable.
On the decoder end, the synthesis is very simple indeed - we just need enough memory to keep track of the n previous samples emitted by the decoder.



  Surely an AVERAGE of these previous samples would be a better indication of the next sample?


This is not true. For example, assume the input signal is a sine wave. The prediction $\hat{y}(n) = (2-\omega^2) y(n - 1) - y(n - 2)$ has zero error, while $\hat{y}(n) = \frac{y(n - 1) + y(n - 2)}{2}$ is wrong most of the time (in particular, it does not capture the fact that the sine wave is strictly increasing half of the time, strictly decreasing the rest of the time, so $y(n)$ shouldn't be "between" the previous values). Speech signals are not sinewaves of course - but you can squeeze much more modelling power out of a model with $p$ parameters (order p AR), than out of a model with zero (averaging).

Also, it's worth keeping in mind that there's a mathematical definition of "better" (minimizing the expected value of the squared of the error), which yields a procedure for finding the optimal value of the coefficients.