What does the degree and order of Spherical Harmonics mean? I've been reading up about Gravitational Models and Spherical Harmonics.

Where I first read about them is in this scholarly article on Autonomous navigation with Gravity Gradients. It talks about Gravity Models being of order x and degree y.

What does order and degree mean in this circumstance? Is it something to do with the Lagrangian Polynomials used in the models?

Another example is found here which states that EGM2008 is complete to spherical harmonic degree and order 2159
It's Legendre polynomials, not Lagrangian.

The zonal harmonics (the $Y^0_l$ terms) depend only on latitude. These zonal harmonics are closely associated with the Legendre polynomials $P_l(x)$, where $x$ is the sine of the geocentric latitude.

The tesseral and sectoral harmonics (the $Y^m_l$ terms, where $m\ne 0$) are closely associated with the associated Legendre functions $P_{lm}(x)$.  (Note: These are sometimes called associated Legendre polynomials, but they aren't polynomials.)

Spherical harmonics are widely used in physics, so the presentations readily found on the internet generally reflect how physicists use spherical harmonics. There are some key differences between these easily found references on the internet and the forms used to represent gravitation. One is that physicists typically use colatitude, and hence use $P_l(\cos\theta)$ as opposed to $P_l(\sin\phi)$. Another is that physicists tend to use the complex form, while gravity models are expressed in terms of real sine and cosine forms. Finally, a set of gravity coefficients is inevitably going to be fully normalized coefficients, while physicists use a form with a different normalization.