Since this answer became a little bit "unreadable",
I created a page with this info.
This is a free interpretation based on these two guides, but I had to change versions and apply some patches to get it to work.
First some basic stuff
sudo apt-get install flex bison libgmp3-dev libmpfr-dev autoconf texinfo build-essential
Then I created a place to store the toolchain (change cj.users to whatever is good for you).
export TOOLPATH=/usr/local/cross-cortex-m3
sudo mkdir /usr/local/cross-cortex-m3
sudo chown cj.users /usr/local/cross-cortex-m3
Binutils
wget http://ftp.gnu.org/gnu/binutils/binutils-2.19.tar.bz2
tar -xvjf binutils-2.19.tar.bz2
cd binutils-2.19
mkdir build
cd build
../configure --target=arm-none-eabi --prefix=$TOOLPATH --enable-interwork --enable-multilib --with-gnu-as --with-gnu-ld --disable-nls
Apply patch to tc-arm.c according this info http://sourceware.org/bugzilla/show_bug.cgi?id=7026 / http://sourceware.org/bugzilla/attachment.cgi?id=3058&action=view
vi ../gas/config/tc-arm.c
make
make install
export PATH=${TOOLPATH}/bin:$PATH
cd ../..
gcc
wget ftp://ftp.sunet.se/pub/gnu/gcc/releases/gcc-4.3.4/gcc-4.3.4.tar.bz2
tar -xvjf gcc-4.3.4.tar.bz2
cd gcc-4.3.4
mkdir build
cd build
../configure --target=arm-none-eabi --prefix=$TOOLPATH --enable-interwork --enable-multilib --enable-languages="c,c++" --with-newlib --without-headers --disable-shared --with-gnu-as --with-gnu-ld
make all-gcc
make install-gcc
cd ../..
Newlib
wget ftp://sources.redhat.com/pub/newlib/newlib-1.17.0.tar.gz
wget http://www.esden.net/content/embedded/newlib-1.14.0-missing-makeinfo.patch
tar -xvzf newlib-1.17.0.tar.gz
cd newlib-1.17.0
Then I would like to apply the patch with something like this (but it did not work)
patch -p1 -i ../newlib-1.14.0-missing-makeinfo.patch
So I opened it manually and edited line 6651 according to the patch.
vi configure
mkdir build
cd build
../configure --target=arm-none-eabi --prefix=$TOOLPATH --enable-interwork --disable-newlib-supplied-syscalls --with-gnu-ld --with-gnu-as --disable-shared
make CFLAGS_FOR_TARGET="-ffunction-sections -fdata-sections -DPREFER_SIZE_OVER_SPEED -D__OPTIMIZE_SIZE__ -Os -fomit-frame-pointer -mcpu=cortex-m3 -mthumb -D__thumb2__ -D__BUFSIZ__=256" CCASFLAGS="-mcpu=cortex-m3 -mthumb -D__thumb2__"
make install
cd ../..
More gcc
cd gcc-4.3.4/build
make CFLAGS="-mcpu=cortex-m3 -mthumb" CXXFLAGS="-mcpu=cortex-m3 -mthumb" LIBCXXFLAGS="-mcpu=cortex-m3 -mthumb" all
make install
Sum up
Now I just added some paths to my ~/.bashrc
#STM32 gcc...
export TOOLPATH=/usr/local/cross-cortex-m3
export PATH=${TOOLPATH}/bin:$PATH
And I should be ready for the next step...