Can we do long division in $\mathbb Z[\sqrt n]$, where $n$ is square free?

Any integral domain that enjoys division with "smaller" remainder, i.e. any Euclidean domain, is necessarily a UFD (unique factorization domain), by essentially the same proof as for $\Bbb Z$. Thus any ring of quadratic integers which is not a UFD will have no such division algorithm. However, there is a (nonconstructive) converse: Weinberger proved in 1973, assuming GRH, that a UFD number ring R with infinitely many units is Euclidean. Thus, for example, real quadratic number rings are Euclidean $\iff$ UFD. However, constructing this Euclidean algorithm can be a very difficult task, e.g. this was proved only in the last decade for $\rm\,\Bbb Z[\sqrt{14}]\,$ (Harper). For a deeper understanding of Euclidean number fields see the excellent surveys by Hendrik Lenstra in Mathematical Intelligencer 1979/1980 (Euclidean Number Fields 1,2,3) and Franz Lemmermeyer's authoritative survey The Euclidean algorithm in algebraic number fields.

However, there is a sort of generalization of the division algorithm that serves to characterize PIDs (number rings, having dimension $\,1\,$ are $ $ UFD $\!\iff\!$ PID). Namely the so-called Dedekind-Hasse criterion states that a domain is a PID iff given any two nonzero elts $\rm\:a, b \in D,\:$ either $\rm\:a\:|\:b\:$ or some D-linear combination $\rm\:a d+bc\:$ is "smaller" than $\rm\,a.\,$ It is clear that such a domain must be PID (since then the "smallest" element in an ideal must divide all others). Conversely, since a PID is UFD, an adequate metric is the number of prime factors (if $\rm\,a\nmid b\:$ then their gcd $\rm\,c\,$ must have fewer prime factors; for if $\rm\:(a,b) = (c)\:$ then $\rm\,c\:|\:a\:$ properly, else $\rm\,a\:|\:c\:|\:b\:$ contra hypothesis). Clearly the Euclidean descent via the Division Algorithm is just a special case, which yields

$$\text{ Euclidean $\Rightarrow$ PID ($\Rightarrow$ \{UFD, Bezout\} $\Rightarrow$ GCD domain})\qquad$$

It is not-so-well-known folklore that these and related results can be generalized to ideals, e.g. as I mentioned on Ask an Algebraist 2008/12/5 there are examples of such results in the papers below. If memory serves correct the first paper sparked a letter to the editor that various results are very old.

Queen, C. Euclidean-like characterizations of Dedekind, Krull, and factorial domains.
J. Number Theory 47 (1994), no. 3, 359--370.

Queen, C. Factorial domains
Proc. Amer. Math. Soc. 124 (1996), no. 1, 11--16.

As for how well the divisibility theory of the ambient ring of integers is (faithfully) reflected in the divisibility of its norms, see this answer.

In general, $\mathbb Z[\sqrt n]$ need not be an euclidean ring.