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.