NOTE
Before you start anything, don't forget to install build-essentials package. Under ubuntu, the command necessary for it is:
sudo apt-get install build-essential - I don't know about other distros..
-------------------------
Well, as promised, now we should write the steps; right?... Now, before we begin, I should really warn that the process is really head spinning if you're to do all by yourself; so take heed to the warnings I give you (I learned the hard way)
Well, first thing is first, we need a Cross Compiler Toolchain, properly built that allows us to build applications, libraries etc. There is one toolchain that's already given to you with Android Native Development Kit (called NDK) but that one is quite restricted because it's built with support for Bionic (trimmed C library that is presented in Android), not Glibc or uGlibC. If you want to develop more native-like applications (especially linux programs) you need GlibC or uGlibC. You can try to build these libraries with that toolchain too, but don't do that, because it's going to fail as well. The reason is that some sort of Chicken-Egg problem is eminent in GlibC-GCC compilation
Let's put the steps to be followed first to build a nice toolchain. I assume you're using Linux - because the tools are developed for this platform only. If you're going to use them in Windows, you need Cygwin or such tools but I can't supply help about that, for since I didn't use them before at all. Google is your friend about this
(Note, the packages I wrote at this list are available at GNU's website
www.gnu.org freely, open source)
1- We're going to build "binutils" first. This package includes some important stuff like assembler, linker, archiver (for libraries) etc..
2- We're going to build GCC's prerequisites. These are GMP, MPRF and MPC packages.
3- We're going to build a "bootstap" gcc (God, I hate that name. I like to call it "naked gcc" more

). This GCC just converts source codes to pure assemblies: thus cannot generate linkages or such. We're going to use it to build "actual" tools we're going to use.
4- We're going to extract Kernel source/headers - use Desire Kernel's here. There is some copying, and such to be done tho.
5- We're going to make GlibC headers installed, which will allow us to build more "complex" gcc, which can link applications with those libraries when the library binaries are given (so such thing is there yet, but we fool it

)
6- We're going to build a very limited GlibC which will give us support for building more "complex" gcc.
7- We're going to build GCC again. This is called "Pass 1 GCC" or "GCC Stage 1". This GCC can link applications to libraries, with the information in Kernel headers and library headers (it's why we give it the headers, so it can create applications suitable with the Kernel architecture).
8- We're to build actual GlibC now. This glibC will be used for our compiled applications, statically or dynamically. You can, at the end of this step, copy the files to your devices and they would work, but picking files here is harder, so I'd recommend you to leave this alone for now

9- We're going to build "Pass 2 GCC" or "GCC Step 2" This is a full fledged GCC that can do anything we want
Complex isn't it? This is precisely why I recommend you to use
Crostool-NG. The other tools (like Buildtools or Crosstool) (sadly) don't create GlibC based toolchains, or use old versions of them, so using this one is recommended. This package automatically will download, setup and link your all toolchain without you worrying about something (believe me, this is what you need. I gave 8 days without this to create a working GCC and Crosstool-NG made another one to me in 50 minutes.

)
Well, however, Crosstool-NG won't create "nice" applications (they'll run allright, but they won't be optimized) without some settings done, so, let's go there. First, we need to install Crosstool-NG itself. To do that; go to
http://crosstool-ng.org/ website, download and extract it to some place. Even though the steps are written in Crosstool website, you don't need all commands there (like setting PATH is unnecessary). The commands you should use is, after CD'ing to the Crosstool dir;
./configure --prefix="</some/place>"
make
make install
cd "</some/place/bin>"
./ct-ng menuconfig
I used prefix as /home/ahmet/crosstool for instance. Note that this is not going to be where your toolchain is, this is where your "toolchain creator" is

.
---- NECESSARY KERNEL HEADER CHANGES ----
OK now, before we start compiling; we need to make some folder moving, copying etc. in Kernel directory. This is needed, because tree structure changed a tad in 2.6 kernels and unless you compiled this kernel before, some directories won't be in their correct place for our cross compiler. Switch to the directory which you extracted the kernel image. Now, from now on, I'm going to assume you're an Qualcomm/MSM board (like Desire, Nexus One etc.) user; but if you're not, change my descriptions accordingly:
1- Go to <kernel dir>/arch/arm/include folder. Copy "asm" directory and paste it into <kernel dir>/include directory.
2- Go to <kernel dir>/arch/arm/mach-msm/include folder. Copy "mach" directory and paste it to <kernel dir>/include/asm directory. It's going to complain that there is another mach folder there and will ask if you want to merge/overwrite. Say yes to all questions.
Now our kernel headers folder is showing a Desire device. Note that if you're not a Desire user, you should use your cpu folder instead of ARM and your board manufacturer in mach-xxxxx instead of mach-msm.
Note this kernel directory, we're going to use it to configure crosstool..
--- CONFIGURING CROSSTOOL ---
After issuing the commands, the crosstool-ng will give you a configuration menu. Most of the setting here are unchanged, but the ones you should change are given below.
1- Paths and misc options
a) Try features marked as EXPERIMENTAL (this is needed to build a toolchain with the latest GlibC support) -> Enabled
b) Local Tarballs directory -> The folder address that you want downloaded stuff to be kept. You might use them again (like for compiling GlibC again for device, you will use them

c) Save New Tarballs -> Enabled ( so that new downloaded files aren't erased

)
d) Working Directory and Prefix directory -> Normally you don't have to change them, but you can if you want to install your toolchain to some other location. CT_TARGET signifies your target name (like arm-msm-linux-gnueabi - arm is cpu model, msm is vendor (can be anything), linux is showing the binaries are for linux system (you can use android, but then you'll get not GlibC but Bionic) and gnueabi shows you're going to use open-source EABI structure for your executables. The other option is ELF but EABI is more flexible (because also supports ELF).
e) Strip all toolchain executables -> do it if you don't want to debug GCC itself. this makes toolchain smaller of size, and a tad faster.
The other options can stay the way they are, or you can change them accordingly here. You can get help with ? key, and if you don't understand anything, just leave them default - there are very complex things there that you don't need to know if you're not planning to be a expert on subject
2- Target options
a) Target Architecture -> arm should be selected, cos Desire uses ARM. If you plan to make toolchain for, say, powerpc, pick that.
b) Endianness -> Should be little. ARM processors in Desire uses little endian system.
c) Architecture level -> "armv7-a" this is should be written. Desire uses ARMv7 based instructions and if you leave here empty, the applications will be built with armv5 support - they're still going to run but not use advanced v7 features.
d) Use Specific FPU -> "neon" . Desire uses NEON structure for floating point arithmetic, and if you leave here empty, the applications will not use Desire's FPU abilities (everything will be software based, which is slower)
e) Default instruction set mode -> arm . You can use thumb here for allegedly faster code but not every build system supports it. Leave it ARM.
f) Use EABI -> enabled. EABI is necessary for most flexible desing of binaries.
The other settings be as they were.
3- Toolchain options
a) Tuple's vendor string -> You can leave here empty if you don't want to; it's not necessary to use a string here. I used "msm" but you can write anything. This string here is used in toolchain name as arm-xxxxx-linux-gnueabi, so make it short, I recommend

b) Tuple's alias -> make it something short like "arm-linux" This alias string is used to make calls to your toolchain easier. Instead of writing arm-msm-linux-gnueabi-gcc everytime, you can use arm-linux-gcc to compile your applications. Can write anything here (like toolchain if you want to use toolchain-gcc to compile your applications)
The other settings can stay as they are, for since default values are the best in our case. You can tweak them only if you know Desire cpu like the back of your hand
4- Operating system
a) Target OS -> Use "linux" if you want the applications to run in Android and Linux; use "bare metal" if you're to compile low level applications which won't use linux headers. Default is linux.
b) Get Kernel headers from -> say "pre installed" because otherwise it's going to download standard Linux headers from internet. We needed some changes, so this option is compulsory to be "pre installed"
c) Path to custom headers directory/tarball -> Path to your kernel source folder - which you made changes above.
WARNING: I say specifically extracted, because standart tarball won't work for us. We're going to make some changes in kernel directories, which is non-standart (Instructions were above).
d) This is a tarball -> No . We're going to use extracted folder.
e) Build shared libraries -> say "yes"; because we want dynamic linkage, not static one

f) Check kernel headers -> say "no" otherwise some unnecessary check causes compilation to stop.
5- Binary utilities
a) Binutils version - pick the latest one, 2.20.1a. If you use older versions with newer GCC/GlibC, it's not going to succeed.
Leave others as they are, they are not big deal..
6- C Compiler
a) GCC Version -> pick 4.6.1 for since it's the latest and most bug free. Just stay away from 4.5

b) Pick the languages you want support for. I've read online that Java is a tad troublesome in Android platform, for since Java in Android uses Dalvik, not Sun systems. You can try it at your second toolchain if you want

Definitely pick C++ tho

c) Link libstdc++ statically -> say yes; it really saves you from big configure scripts later

- apparently needed to avoid PPL problems as well

d) Compile lidmudflap/libgomp/libssp -> say no. These libraries are not the most suitable libraries for ARM platform (at least at cross-compiler level. You can compile them later, if you want, with your cross-toolchain.)
You can leave others as default
7- C library
a) C library -> gLibC (recommended). You can use other libraries which are eGlibC (embedded Glibc, like Bionic) and uGlibC (micro-glibc) too, but GlibC is the most spanning solution above those. The libraries are bigger, but they support more.
b) glibC version -> Use 2.13 (experimental) it compiles just fine, and you get a new version of GlibC. Not the newest, but that's ok

c) Threading implementation -> nptl (recommended) . You can use linuxthreads too, but nptl is more advanced ( like giving support to Thread-Local-Storage and such)
d) Force Unwind Support -> Enabled . If you don't use this option, for since we're making this toolchain from scratch, it's going to give you error during compiling that it couldn't find necessary headers (we're building them now, dumbass!)
Leave others default if you don't know what they're about
8- Companion Libraries
Well, go and pick the latest versions, even though when it says "Experimental", otherwise your GCC compilation will give you error about these libraries being old.
After setting these settings, press ESC key twice till it goes way back and ask if you want to save configuration; say yes.
--- STARTING COMPILATION ---
Now to start compilation write
./ct-ng build.
This is going to take approx. 45 minutes, so go watch some episodes of Big Bang Theory or something. Normally, there should be no errors but if there is; most probably either you made a wrong configuration, or didn't set your kernel folders well. Try again with other settings, google your problem etc..
After this process, you're going to have a cross-compiler at your use at /home/<username>/x-tool/arm-<vendor>-linux-gnueabi/bin folder. Note that Crosstool-NG automatically makes this folder read only to make you prevent screwing your toolchain

You must edit your path variable to show "/home/<username>/x-tool/arm-<vendor>-linux-gnueabi/bin" folder as well for less headaches during compiling later
Whilst compiling other application, most used configure options you're going to use is "--host=arm-<vendor>-linux-gnueabi" and "--prefix=/some/folder/you/want/this/application/copied". After compilation, you can send binaries to your phone from prefix folder.
More options about GCC and Configure is available at GCC and Autoconf man pages; check them as well
Happy cross-compiling people