Warning: In the physical literature the epithet "Markov" is often used with regrettable looseness. The term has a magical appeal, which invites itself in an intuitive sense not covered by the definition. [...] it is meaningless to ask whether or not it is Markovian, unless one specifies the variables to be used for its description.
That warning is a quote from one of the most famous books in matter modeling: "Stochastic Processes in Physics and Chemistry" by Nico van Kampen. The book has 15967 citations on Google Scholar at the moment, and that specific quote has been reused elsewhere, such as in this free PDF book on Pg. 51.
When a process is Markovian, it essentially means that the probability density function at time $t_{n+1}$ can entirely be obtained from the function's current value at $t_n$, and does not depend explicitly on previous times such as $t_{n-1}, t_{n-2},$ etc. It has no memory of the past.
The definition can be generalized beyond just probability distribution functions, because (for example) in quantum mechanics we have the density matrix where the diagonals are probabilities, but the off-diagonals are something that doesn't even exist in classical theory. If the density matrix evolves like:
$$\tag{1}
\rho(t_{n+1}) = e^{-\frac{\textrm{i}}{\hbar}Ht_{n+1}}\rho(t_n)e^{\frac{\textrm{i}}{\hbar}Ht_{n+1}}
$$
then the evolution we can obtain $\rho(t_{n+1})$ from only $\rho(t_{n})$. Then we can obtain $\rho(t_{n+2})$ from only $\rho(t_{n+1})$, and $\rho(t_{n+3})$ from only $\rho(t_{n+2})$, and what we get is a Markov chain.
If we ignore gravity (for which we don't yet have a quantum theory), we can say that the whole universe undergoes Markovian evolution according to Eq. (1). But if we want to look at a sub-system of the universe (such as a peptide molecule), then we cannot just calculate $\rho_{\textrm{subsystem}}(t_{n+1})$ by just knowing $\rho_{\textrm{subsystem}}$ at some previous time such as $t_{n}$, the evolution of $\rho_{\textrm{subsystem}}$ will require starting at $\rho_{\textrm{subsystem}}(t=0)$ and doing a Feynman integral over all the history of what the rest of the universe did to the subsytem (for example, see Eq. 8 of my paper which described an open source MATLAB code to easily calculate this Feynman integral).
So neglecting gravity, quantum mechanics tells us that the evolution of the universe is Markovian, and the evolution of any sub-system of the universe (such as a peptide molecule) that is not completely isolated from the influence of any other part of the universe, undergoes non-Markovian evolution.
Here the variable to which I'm referring is the density matrix. Since non-Markovian dynamics can be hard to calculate, we often approximate the dynamics by a Markovian master equation but this is an approximation to the true non-Markovian dynamics of any system that is not the entire universe (including vacuum vibrations in QED) itself.
Now in classical MD, which is an approximation of quantum dynamics, but good enough for most studies (!), the answer by dwhswenson points out that if considering the full phase space (analogous to the full universe, in my above description), then the probability of going to another state follows Markovian dynamics in that it only depends on the current state (positions and velocities of all particles, notices that the we are specifying all the "variables" that van Kampen warns us to make sure we specify!). Notice also that any slight influence from outside a subsystem (i.e. from the rest of the universe) can bring the subsystem out of its equilibrium, and that his answer also says that for this non-equilibrium dynamics, the Markov approximation is no longer valid. Regarding the rest of his answer, it's certainly possible very often to approximate dynamics by a Markov process, and whether or not these approximations are sufficient for your purposes will depend on your specific study.