The kernel is a given, but don't forget that the same Linode-provided kernel is used regardless of which distribution you choose, even if you choose it from the Distro Wizard. In other words, it's not distro-specific; in fact, very few kernels nowadays will be distro-specific, since most will compile everything in a modular fashion. The kernel provided by Linode is monolithic, but that's okay because the hardware on each Linode is, I suspect, the same or very close. (Does UML emulate specific hardware or is everything virtualised?)
To actually roll your own distro you'll need to be aware of the steps at
http://www.linode.com/wiki/index.php/Cu ... stribution to get it working properly on Linode. Otherwise, you should be able to proceed as with a normal distro, I guess.
Although this does bring to mind one question I have, if anybody can answer it - what happens so far as boot loaders go?