Most of the embedding theorems I know come with constructions, some more explicit than others, of the required embedding. Some embeddings are made explicitly from other functions, others are the result of a limit process or recursive process that can be shown to have the right properties.
Examples of the latter are: every countable linear order embeds into $\mathbb{Q}$, which has a nice recursive proof.
That an uncountable linear order could never be so embedded is of course trivial from the fact that $\mathbb{Q}$ is countable.
An example of the former: every $T_0$ topological space $X$ can be embedded into a product of copies of the two-point Sierpinski space $S = (\{0,1\}, \{\emptyset, \{0\}, \{0,1\}\})$. The proof is just that for every open set $O$ of $X$ we pick $f_O: X \to S$ defined by $f_O(x) = 0$ if $x \in O$, $f(x) = 1$ if $x \in X\setminus O$. These maps are all continuous, and a standard embedding theorem tells us that $e(x) = (f_O(x))_{O \in \mathcal{T}_X}$ is an embedding of $X$ into $\prod_{O \in \mathcal{T}_X} S$.
Because all products and subspaces of $T_0$ spaces are also $T_0$, it's only $T_0$ spaces for which this can work. So there are good reasons for non-embeddibility.
A similar example we have in Tychonoff spaces and products of $[0,1]$ (Tychonoff cubes).
It's also a well-known embedding theorem (more alnog your lines, I think) that says that any separable metric space with $\dim(X) = n$ can be embedded into $\mathbb{R}^{2n+1}$, and for compact (differential) manifolds this can be improved to $\mathbb{R}^{2n}$. The proof of the first embedding (that I know of) is a limiting process of mapping into Nöbeling space, and the second one uses machinery from differential manifolds and integration, IIRC.
Non-embedding theorems can be hard (one of the simplest cases for dimension being the "utilities graph" $K_{3,3}$ not being planar (embeddable into $\mathbb{R}^2$). (The graph is a compact one-dimensional simplex, but not a manifold, so no problem with the second theorem above), and all graphs can be embedded into $\mathbb{R}^3$ (but this is quite explicitly possible and needs no big theorems per se)
The non-embeddibility follows in this case from arguments involving Euler characteristic : there is a property of the plane that inherits down to its sub-simplices, and $K_{3,3}$ does not have it.
