Does the Hasse norm theorem easily imply the global squares theorem?

I'm not sure how constructive the following answer to your second question is. If $\alpha$ is not a square, then there must exist a prime ideal ${\mathfrak p}$ coprime to $2\alpha$ with $(\alpha/{\mathfrak p}) = -1$. This follows from Kronecker's density theorem according to which the density of the prime ideals that split completely in a normal extension $L/K$ is equal to $1/(L:K)$. All you need for a proof is that the Dedekind zeta function of a number field $F$ has the property that $(s-1) \zeta_F(s)$ has a finite limit as $s \to 1$.

Once you have such a prime ideal ${\mathfrak p}$, take any quadratic extension $L/K$ in which ${\mathfrak p}$ ramifies (you might pick an ideal ${\mathfrak a}$ in the inverse class, write ${\mathfrak p}{\mathfrak a} = (\beta)$, and set $L = K(\sqrt{\beta})$, for examples), and $\alpha$ will not be a norm from $L$.

I would be suprised if you could construct ${\mathfrak p}$ "explicitly". Take e.g. the case where $\sqrt{\alpha}$ generates the Hilbert class field of a number field $K$ with class number $2$; then you would have to find a nonprincipal prime ideal in $K$.The fastest solution in this case is, as far as I know, picking prime ideals at random.

Well, I would say that this crucially depends on what you define to be "quick". If you admit global class field theory, at least in its idelic formulation, the fact that all primes in $K$ are split in the extensions $K(\sqrt{x})/K$ proves that $x$ is a square quite rapidly (as Timo Keller has observed in the comments, this is actually easier than Chebotarev; and Franz Lemmermeyer's answer says even more). I give a short proof at the end of my answer, although it does not "need" the global norm theorem (which is anyhow hidden beneath the idelic formulation of global class field theory). I am pretty sure that this is the proof you have in mind when you ask for a quicker one.

Without class field theory, I could come up only with an "elementary" proof assuming that

[H1] $K$ admits at least one real embedding, let it be $\sigma\colon K\hookrightarrow \mathbb{R}$, and

[H2] $K/\mathbb{Q}$ is unramified at $2$.

Consider then the following

Claim An element in $\mathcal{O}_K\setminus\{0\}$ is a square if and only if it is a (global) norm from every quadratic extension $L/K$

Admit the claim: we are going to deduce that if an element $x=r/s$ with $r,s\in\mathcal{O}_K$ is locally a square everywhere, then $x\in(K^\times)^2$. Let $y=xs^2$: then $y\in\mathcal{O}_K\setminus\{0\}$ is locally a norm from every quadratic extension $L/K$, since it is a square in $K_\mathfrak{p}^\times$ for all $\mathfrak{p}$. By the global norm theorem it is a global norm from every quadratic extension, and the claim tells you $y\in (K^\times)^2$: hence the same holds for $x=y/s^2$.

To prove the claim, observe that one direction is obvious: squares are norms from every quadratic extension. On the other hand, let $x\in\mathcal{O}_K\setminus\{0\}$ be a norm from every quadratic extension. I will use the real embedding $\sigma$. Consider the function $$ f\colon \mathcal{O}_K\times\mathcal{O}_K\setminus \{0\}\longrightarrow \mathbb{R} $$ sending $(a,b)$ to $f(a,b)=\sigma\left(\left(\frac{a}{b}\right)^2-\frac{x}{b^2}\right)$. Then there is a bound $B\in\mathbb{R}$ such that $\mathrm{Im}(f)\subseteq [B,+\infty)$. Indeed, $(a/b)^2\geq 0$, while $b\mapsto x/b^2$ is bounded from below, since $\sigma(\mathcal{O}_K)$ is discrete. Chose now a prime number $\ell\equiv 3\pmod{4}$ which is unramfied in $K/\mathbb{Q}$ and such that $-\ell<B$. Consider the extension $K(\sqrt{-\ell})/K$: since the discriminant of $\mathcal{O}_K(\sqrt{-\ell})/\mathcal{O}_K$ is $-4\ell$ and the ideal $\ell\mathcal{O}_K$ is square-free by assumption, it follows that $[\mathcal{O}_L:\mathcal{O}_K(\sqrt{-\ell})]=1,2$. Since we assumed that $K/\mathbb{Q}$ be unramified at $2$, the same argument as above implies that $\mathcal{O}_{K(i)}=\mathcal{O}_K[i]$ and then that $x^2+y^2\equiv 0\pmod{4\mathcal{O}_K}$ has the unique solution $x\equiv y\equiv 0\pmod{4\mathcal{O}_K}$ (because each prime $\mathfrak{r}\mid 2$ of $\mathcal{O}_K$ is ramified in $K(i)/K$, hence if something has norm from $K(i)$ to $K$ which is divisible by $4$, it must lie in $2\mathcal{O}_K[i]$): in particular, the usual proof that the ring of integers of the imaginary quadratic field $\mathbb{Q}(\sqrt{-\ell})$ is $\mathbb{Z}[\sqrt{-\ell}]$ carries over, and $[\mathcal{O}_L:\mathcal{O}_K(\sqrt{-\ell})]=1$.

Since we assumed that $x$ is a norm from $K(\sqrt{-\ell})/K$, we get $x=a^2+\ell b^2$ for suitable $a,b\in\mathcal{O}_K$, by the above discussion. If $b=0$, then $x$ is a square, and we win. If not, rewrite the equality as $$ \frac{a^2-x}{b^2}=-\ell\Longrightarrow \sigma(-\ell)=-\ell=f(a,b) $$ This contradicts the fact that $\mathrm(Im)(f)\subseteq [B,+\infty)$ and finishes the proof of the claim, but I realise that one can reasonably object that the above proof is not "quick"...

One final comment about assumption [H2]. It was only needed above to be sure that $\mathcal{O}_{L}=\mathcal{O}_K[\sqrt{-\ell}]$. This is not necessary: one could do, for instance, by proving that there must exist a $\delta$ with $\sigma(-\delta)<B$ and $\mathcal{O}_{K(\sqrt{-\delta})}=\mathcal{O}_K[\sqrt{-\delta}]$. Or, if one assumes that $2\notin (K^\times)^2$, then also the case $[\mathcal{O}_{L}\colon\mathcal{O}_K]=2$ can be treated, by modifying a bit $f(a,b)$. But I could not do much better, hence I left assumption [H2], although probably too restrective.

Now, with global class field theory. The extension $L=K(\sqrt{x})/K$ is abelian and corresponds to a unique normic subgroup $\mathcal{H}\subseteq C_K$ where $C_K$ is the idèle class group of $K$, so $\mathcal{H}=\mathrm{Norm}_{L/K}(C_L)$. Your assumption that $x\in (K_\mathfrak{p}^\times)^2$ for all primes $\mathfrak{p}$ means that $\mathrm{Norm}_{L_\mathfrak{P}/K_\mathfrak{p}}(L_\mathfrak{P}^\times)=K_\mathfrak{p}^\times$ for all $\mathfrak{p}$ and all $\mathfrak{P}\mid\mathfrak{p}$ (caution: we are using here that the minimal polynomial for $x$ has degree $1$ or $2$. Indeed, saying that $x\in (K_\mathfrak{p}^\times)^2$ is equivalent to saying that all roots of $X^2-x$ are in $K_\mathfrak{p}$, but this can be false if we replace $X^2-x$ by $X^n-x$ and try to prove the analogous statement replacing "square" by "$n$th power"). Then $\mathrm{Norm}_{L/K}(C_L)=C_K$ and hence $L=K$, or $x\in(K^\times)^2$. This is an adaptation of Corollary 8.8 in Tate's article on Global Class Field Theory in Cassels and Fröhlich's Algebraic Number Theory.