Uniqueness for the heat equation fails on unbounded domains, without some additional growth restrictions on the solution.
Here is an example:
$$u(x,t) = \sum_{n=0}^\infty \frac{g^{(n)}(t)}{(2n)!} x^{2n}$$
where
$$g(t) = \begin{cases} e^{-\frac{1}{t^2}},&\text{if } t>0\\
0,&\text{if } t\leq 0.\end{cases}$$
The function $u$ satisfies the heat equation $u_t = u_{xx}$ on the entire real line $\mathbb{R}\times(0,\infty)$, and $u(x,0)=0$ (the zero function is also a solution). There are in fact infinitely many solutions constructed this way, and the construction can easily be adapted to a half line.
Notice the function $u$ grows exponentially fast as $x \to \pm \infty$ (compare it to the Taylor series for $\cosh(x)$ for example). This corresponds to an infinite amount of heat propagating in from $x=\pm \infty$ in finite time, and for this reason is considered a "non-physical" solution of the heat equation. It is possible to use the maximum principle to prove that there is a unique solution satisfying the growth estimate
$$u(x,t) \leq A e^{ax^2}$$
where $A,a>0$ are arbitrary constants. You can find the proof of this in Chapter 2 of L.C. Evans PDE textbook (Section 2.3.3).
The proof is a fair bit easier if we assume the solutions are bounded. I'll sketch the proof here. Let $u(x,t)$ be a bounded solution of the heat equation $u_t = u_{xx}$ on $\mathbb{R}\times (0,\infty)$ satisfying $u(x,0)=0$. By bounded I mean that $|u(x,t)|\leq C$ for all $(x,t)$, where $C>0$ is some constant.
We want to show that $u(x,t)=0$, as this is the physically reasonable solution with zero initial conditions. The difficulty with using the maximum principle directly is that $u$ may not attain its maximum value on the unbounded domain. So we have to find some way of replacing the entire real line with a bounded interval.
Along these lines, consider the following: Let $\varepsilon>0$, $a \in \mathbb{R}$ and define
$$v(x,t) = u(x,t) - (2t + (x-a)^2)\varepsilon$$
Check that $v(x,t)$ is again a solution of the heat equation $v_t=v_{xx}$. Now consider a very big rectangle $R=[a-N,a+N] \times [0,T]$ where $N>0$ is large. By the usual maximum principle, $v$ must attain its maximum value over $R$ on the sides or base of the rectangle. On the sides we have
$$v(x,t) \leq C-(N-a)^2\varepsilon \leq 0$$
provided we choose $N$ sufficiently large. On the base we have $u(x,0)=0$ so
$$v(x,t) \leq -(x-a)^2\varepsilon \leq 0.$$
Therefore $v\leq 0$ throughout the rectangle $R$. In particular,
$$v(a,t) = u(a,t) - 2t\varepsilon \leq 0$$
and so $u(a,t) \leq 2t\varepsilon$ for all $t \in [0,T]$. We can send $\varepsilon \to 0^+$ and $T\to \infty$ to find that $u(a,t)\leq 0$ for all $t\geq 0$. Since $a\in \mathbb{R}$ was an arbitrary real number, we have that $u\leq 0$ everywhere. Since $-u$ satisfies the same heat equation, we also have $-u \leq 0$, so $u=0$.
Thus, the only bounded solution of the heat equation on the entire real line with zero initial data is the zero function $u=0$. From this, you can easily show that bounded solutions with the same initial data are unique (use linearity of the PDE).
The proof from Evans PDE book using the exponential growth estimate is similar, except that the definition of $v$ is more clever. All of these arguments can be easily adapted to half lines as well.
Best Answer
Anytime you see a finite domain, standard heat equation, think separation of variables. Try to use $u(x,y,t) = T(t)X(x)Y(y),$ and you'll get 3 ODE's to solve, something along the lines of \begin{align} T'(t) + c^2(\lambda_x + \lambda_y)T(t) &= 0\\ X'' - \lambda_x X &=0\\ Y'' - \lambda_y Y &=0. \end{align} This should be the motivated approach by seeing the form of the solution, namely 3 functions, each of a single variable, multiplied together. Try it and see how it goes.
A little intuition behind why $m \leq u(x,t) \leq M$ is as follows,
The solution form is exponentially decaying in time, and the trig functions are bounded, so for $t$ growing, the solution relaxes (Show this rigorously by bounding the size of your solution). When $t$ is zero, the solution satisfies the boundary conditions, and those are bounded as well. It is not hard to translate this into a mathematical statement.