We just need Stampacchia's theorem:
Theorem: Let $\Omega\subset \mathbb{R}^N$ be a bounded domain, $p\in [1,\infty)$ and $G:\mathbb{R}\to \mathbb{R}$ a Lipschitz function with bounded derivative. Then, if $u\in W^{1,p}(\Omega)$, it is also true that $G(u)\in W^{1,p}(\Omega)$ with $\nabla (G(u))=G'(u)\nabla u.$
The proof should be straightforward if one knows something about absolutely continuous functions. See for example the book Partial Differential Equations by Evans for the $C^1$ case and Weakly Differentiable Functions by Ziemer for the general case.
Now, if $G(x)=\max\{x,0\}$ then, $G$ is Lipschitz with derivative bounded by $1$ therefore, if $u\in W^{1,p}(\Omega)$ then $G(u)=\max\{u,0\}\in W^{1,p}(\Omega)$ and
$$\nabla (G(u)) = \begin{cases} \nabla u & \mbox{if } u\ge0 \\ 0 & \mbox{if } u\le0 \end{cases}.$$
To conclude, note that $\min\{u,v\}=-\max\{u-v,0\}+u$ which implies that
$$\nabla (\min\{u,v\}) = \begin{cases} \nabla v & \mbox{if } u\ge v \\ \nabla u & \mbox{if } u\le v \end{cases}.$$