As a first remark, since it was commented that the problem is autonomous one can use instead of a quadratic constant Lyapunov function, an also quadratic Lyapunov function but depending on $x$.
In this case, instead of
$$ \mathbf A(x) ^T \mathbf M + \mathbf M \mathbf A(x) =-\mathbf{N} $$ one has
$$ \mathbf A(x) ^T \mathbf M(x) + \mathbf M(x) \mathbf A(x) =-\mathbf{N}, $$
or equivalently,
$$\mathbf A(x) ^T \mathbf M(x) + \mathbf M(x) \mathbf A(x) \prec 0,$$ where $\prec$
is the Loewner order on the space of the symmetric matrices.
This matrix inequality is an instance of what is called in the literature as a parameterized linear matrix inequality (PLMI) and although it is known that the problem to find a feasible solution to a generic PLMI is NP-hard, it is possible to use relaxations techniques that turn this problem into a standard LMI problem, but potentially conservative (1).
In special, when the PLMI is the Lyapunov equation, it is worth to mention a case which is frequently seen in the robust control literature, namely when $x \in \Delta_N$, where $\Delta_N$ is the N-simplex, and $\mathbf{A}$ is linear.
Then, one may say that $\mathbf{A}$ is in a polytopic domain and that $x$ represents the uncertainty about matrix $\mathbf{A}$.
For this special case, it was proved that by imposing a homogeneous polynomial structure in $\mathbf{M}$ and using a generalization of Pólya's inequality to matrices with homogeneous polynomial structure, one can design sufficient LMI conditions which tends to equivalent conditions to the original PLMI. For more, see (2) and the references therein.
(1) Apkarian, P., & Tuan, H. D. (2000). Parameterized LMIs in control theory. SIAM Journal on Control and Optimization, 38(4), 1241–1264.
(2) Oliveira, R. C. L. F., & Peres, P. L. D. (2007). Parameter-Dependent LMIs in Robust Analysis: Characterization of Homogeneous Polynomially Parameter-Dependent Solutions Via LMI Relaxations. ieeetac, 52(7), 1334–1340.
