I am considering a linear dynamical system of the form
$$x_{k+1} = Ax_k$$
I know that when we have stability (that is, that $x_k$ goes to $0$ as $k$ approaches infinity), there exists an $n$-by-$n$ matrix $P$ such that $P$ is positive-definite and $P-A^TPA$ is positive definite; that is, there exists a Lyapunov function of the form
$$V(x) = x^T P \, x$$
Suppose that we are given $A$, and I want to find the matrix $P$. I know that this problem is a semidefinite programming relaxation given the constraints on $P$, but I am unsure how to define this SDP in terms of writing the objective. How would I define the SDP to solve for $P$?
It is not a semidefinite relaxation, it is a semidefinite program. Relaxation means outer approximation, but this is an exact model.
As mentioned, you can plug this feasibility problem into several available packages such as CVX or YALMIP. Here's an example in YALMIP (continuous time but the change you have to do is trivial) https://yalmip.github.io/tutorial/semidefiniteprogramming/
Of course, if you don't have any more constraints, there is no need to pose the problem as an optimization problem, but you can simply solve the equation using more efficient numerical methods (such a dlyap in MATLAB)