Here I am going to explain how to build custom Linux kernel on Ubuntu. I am using Hardy Heron (Ubuntu 8.04).
One need to have some specific packages for compiling Linux kernel. These packages are kernel-package, libncurses5-dev and fakeroot. The way to install these packages is to run following commands in order.

avinesh@avinesh-desktop:~$ sudo apt-get update 

This will update the local package database with the information of latest version.

avinesh@avinesh-desktop:~$ sudo apt-get install kernel-package libncurses5-dev fakeroot 

For downloading the packages and installing it.

I am not going into the details of kernel configuration however the easy way is to copy the config file used by running kernel or the config file of most close kernel version which is working fine to the root
directory of Linux kernel as file with name .config.

avinesh@avinesh-desktop:~/linux-2.6.25.8$ cp /boot/config-2.6.24-19-generic  .config

Now the step is to do any specific kernel configuration if required, I prefer running configuration tool in ncurses mode. Following command runs configuration tool in text mode.

avinesh@avinesh-desktop:~/linux-2.6.25.8$ make menuconfig

Save the configuration changes and exit out of the tool.

Next step now is to start compiling the kernel. The commands to do that are ...

avinesh@avinesh-desktop:~/linux-2.6.25.8$ make-kpkg clean
avinesh@avinesh-desktop:~/linux-2.6.25.8$ fakeroot make-kpkg --initrd --append-to-version=-custom kernel_image kernel_headers
 

Here the '--append-to-version' option is used to differentiate between different builds of the same kernel.

So now the kernel and its header files are ready to be installed.

avinesh@avinesh-desktop:~$ sudo dpkg -i linux-image-2.6.25.8-custom_2.6.25.8-custom-10.00.Custom_i386.deb
avinesh@avinesh-desktop:~$ sudo dpkg -i linux-headers-2.6.25.8-custom_2.6.25.8-custom-10.00.Custom_i386.deb

Now the kernel is ready to boot into.