Way to memorize relations between the Sobolev spaces? Consider the Sobolev spaces $W^{k,p}(\Omega)$ with a bounded domain $\Omega$ in n-dimensional Euclidean space. When facing the different embedding theorems for the first time, one can certainly feel lost. Are there certain tricks to memorize the (continuous and compact) embeddings between the different $W^{k,p}(\Omega)$ or into $C^{r,\alpha}(\bar{\Omega})$ ?
 A: Sobolev norms are trying to measure a combination of three aspects of a function: height (amplitude), width (measure of the support), and frequency (inverse wavelength).  Roughly speaking, if a function has amplitude $A$, is supported on a set of volume $V$, and has frequency $N$, then the $W^{k,p}$ norm is going to be about $A N^k V^{1/p}$.
The uncertainty principle tells us that if a function has frequency $N$, then it must be spread out on at least a ball of radius comparable to the wavelength $1/N$, and so its support must have measure at least $1/N^d$ or so:
$V \gtrsim 1/N^d.$
This relation already encodes most of the content of the Sobolev embedding theorem, except for endpoints.  It is also consistent with dimensional analysis, of course, which is another way to derive the conditions of the embedding theorem.
More generally, one can classify the integrability and regularity of a function space norm by testing that norm against a bump function of amplitude $A$ on a ball of volume $V$, modulated by a frequency of magnitude $N$.  Typically the norm will be of the form $A N^k V^{1/p}$ for some exponents $p$, $k$ (at least in the high frequency regime $V \gtrsim 1/N^d$).  One can then plot these exponents $1/p, k$ on a two-dimensional diagram as mentioned by Jitse to get a crude "map" of various function spaces (e.g. Sobolev, Besov, Triebel-Lizorkin, Hardy, Lipschitz, Holder, Lebesgue, BMO, Morrey, ...).  The relationship $V \gtrsim 1/N^d$ lets one trade in regularity for integrability (with an exchange rate determined by the ambient dimension - integrability becomes more expensive in high dimensions), but not vice versa.
These exponents $1/p, k$ only give a first-order approximation to the nature of a function space, as they only inspect the behaviour at a single frequency scale N.  To make finer distinctions (e.g. between Sobolev, Besov, and Triebel-Lizorkin spaces, or between strong L^p and weak L^p) it is not sufficient to experiment with single-scale bump functions, but now must play with functions with a non-trivial presence at multiple scales.  This is a more delicate task (which is particularly important for critical or scale-invariant situations, such as endpoint Sobolev embedding) and the embeddings are not easily captured in a simple two-dimensional diagram any more.
I discuss some of these issues in my lecture notes
http://terrytao.wordpress.com/2009/04/30/245c-notes-4-sobolev-spaces/
EDIT: Another useful checksum with regard to remembering Sobolev embedding is to remember the easy cases:


*

*$W^{1,1}({\bf R}) \subset L^\infty({\bf R})$ (fundamental theorem of calculus)

*$W^{d,1}({\bf R}^d) \subset L^\infty({\bf R}^d)$ (iterated fundamental theorem of calculus + Fubini)

*$W^{0,p}({\bf R}^d) = L^p({\bf R}^d)$ (trivial)


These are the extreme cases of Sobolev embedding; everything else can be viewed as an interpolant between them. 
EDIT: I decided to go ahead and draw the map of function spaces I mentioned above, at
http://terrytao.wordpress.com/2010/03/11/a-type-diagram-for-function-spaces/
A: To see whether a $W^{k,p}$ space embeds in another, compare their $k-n/p$.  To see if it embeds in a $C^{m,\alpha}$ space, compare it to $m+\alpha$.  I don't know if that counts as easy to remember, but it works for me.
Of course, there's more to the theorem than what I wrote, but I think I've summarized the easily-forgotten part.
A: I once went to a talk (sorry, forgot by whom) where all the Sobolev spaces were plotted in $R^2$, with $k$ on the vertical axis and $1/p$ on the horizontal axis. In this diagram, the "critical embeddings" lie on lines with slope $n$. Given a space $W^{k,p}$, the spaces that can be continuously embedded in it lie above it in the diagram and to the right of the line through $W^{k,p}$ with slope $n$. 
PS: I hope I remember correctly, and that somebody will correct me otherwise.
A: Just want to second Jack's use of scaling argument. For direct Sobolev to Sobolev embeddings the scaling is easy to come-by (as long as you remember that you can shrink but not expand, unlike the unbounded domain case). For Sobolev to Holder, I find it helpful (for the scaling argument) to replace Holder spaces by their Besov characterizations $B^{s,\infty}_\infty$. In terms of Littlewood-Paley characterizations, the "one way" scaling tells you that you can try to make things bad at infinity in frequency space and not near zero. These usually work very well for the non-endpoint cases. The end-point case you can figure out what the critical exponents are by scaling, and then you just need to remember the qualitative information about compactness of the embedding and the general intuition that increasing the differentiability $k$ and the integrability $p$ both make the Sobolev space "better".  
Technically speaking, this is not memorizing, but figuring it out on the fly.
I remember asking my PhD advisor this same question when I was a first year in graduate school. He told me that memorizing something that can be looked up in 5 minutes in any textbook in a waste of time and energy. 
A: The way I remember is that the embedded space must have more smoothness, and the additional smoothness that is required gets larger when the difference in $1/p$ gets larger. Then you have to divide the smoothness by $n$, so there will be fraction lines everywhere. So a necessary condition for $W^{s,p}\hookrightarrow W^{r,q}$ is
$$
\frac{s-r}{n} \geq \frac1p - \frac1q.
$$
A: Exactly as Dan Lee says, the key is the "weight" $k-n/p$ of the Sobolev space $W^{k,p}$. To remember the weight, you can use scaling, just as the other answers and comments suggest, but there is a cheap trick which is much simpler than changing the function whose norms you are considering. 
Instead, multiply the metric by a constant R. This will scale the $W^{k,p}$-norm by $R^{n/p-k}$ and the $C^{m,\alpha}$-norm by $R^{-(m+\alpha)}$. From here you see immediately the relevance of the weights and the direction in which the embeddings must go. 
A: Here is my two-cent insight based on the physicists obsession with units. Suppose  you are interested in a Sobolev $(k,p)$-norm  on an $N$-dimensional  Riemann manifold  $(M,g)$,
$$\Vert u\Vert_{k,p} =\left(\int_M |\nabla^k u|^p dV_g\right)^{1/p}. $$
We start by observing that $\nabla^k u$  is measured in $meters^{-k}$ (think that $\nabla^k u=d^ku/dx^k$ and $dx$ is measured in $meters$ while $u$ is a dimensionless quantity, i.e., $0$-density). Hence $|\nabla^k u|^p$ is measured in $meters^{-kp}$. The volume density $dV_g$ is measured in $meters^N$ so that $\int_M |\nabla^k u|^p dV_g$ is measured in  $meters^{N-kp}$. This shows that $\Vert u\Vert_{k,p}$ is measured  in $meters^{N/p-k}$.   Set 
$$w_N(k,p):= N/p-k. $$
Then on compact manifolds we have continuous  embedding 
$$ W^{k_1,p_1}\subset W^{k_2,p_2}  \Longleftrightarrow  -k_1 \leq -k_2,\;\;w_N(k_1,p_1)\leq w_N(k_2,p_2).$$
The embedding is compact  if   the inequalities in the right-hand-side are strict. To include the Holder spaces in this story think
$$C^{k,\alpha}= W^{k+\alpha, \infty}.$$
