Multi-dimensional models
In the 2D case, $x_t$ is a vector with two components (e.g. position in $x$, $y$), but why stop at 2D? Often, the state vector $x_t$ will have your position in two or three dimensions, in addition to velocity and acceleration. Oftentimes we also include angular state in $x_t$ such as the heading and angular rate of change.
Your control is also often multi-dimensional, for example if you have a wheeled robot it could be the velocity of the left and right wheels.
Linear case (Kalman filter!)
Typically we have a model that maps the previous state and control actions to a new state and control action. In the linear, time invariant case, we have matrices $A$ and $B$, and
$$x_t = A x_{t-1} + B u_t $$
in this setting we would probably use a Kalman filter to keep track of our belief about the distribution of $x_t$. The Kalman filter is nice because it gives a closed form solution to the estimation problem which is correct if noise/uncertainty is Gaussian.
More general models
The markov approach (as I understand it) let's us move past these assumptions (linearity and Gaussian noise) by using approximation methods such as particle filters to estimate the belief distribution of our state $x_t$. The markov assumption is saying that we only need the distribution of $x_t$ (and don't need to use the distribution of $x_{t-1},x_{t-2},\dots$) when computing the distribution of $x_{t+1}$. I think the figure on slide 30 of the link you posted illustrates this quite well.
Discrete (small) state space
As for your last question about how to find your belief: it depends on your application. If your state/controls are discrete, and you don't have very many of them, you can explicitly write down all of the transition probabilities $p(x_t \mid x_{t-1}, u_t)$ for every possible $x_t$, $x_{t-1}$ and $u_t$. Then when you do your estimation, you just look up the appropriate value.
Further reading
Typically states are continuous, or there are too many to compute/store every possible transition. If you're just getting started in this, try a Kalman filter and see how that works for you (there are many tutorials on them). If you want to see what else is out there, I recommend the Probabilistic Robotics book, which gives a still quite good overview of different approaches (including Kalman filters) for this localization problem.
