I recently had to re-compile a kernel, and there's a few preliminaries. You need to install a bunch of packages :
sudo apt-get install fakeroot build-essential crash kexec-tools makedumpfile kernel-wedge sudo apt-get install kernel-package
After that you can follow the excellent guide here:
One point which I had missed though is where are the packages once you've finished compiling (although it's written in the guide). So if like they recommend in the you've extracted the kernel source under ~/src/linux-source-2.6.35 for instance, then the deb packages will be in ~/src.
Enjoy.