(As all the guides I found out there were either outdated or specific to windows/cygwin, I decided to put this here just so that I remember how to do this next time I have to install the toolchain on another computer :-) )
First, check out the toolchain sources from svn://svn.ps2dev.org/psp/trunk/psptoolchain into say ~/tmp/psptoolchain:
mkdir ~/tmp/psptoolchain cd ~/tmp/psptoolchain svn co svn://svn.ps2dev.org/psp/trunk/psptoolchain .
Notice the svn:// and not http://, most tutorials are still using http://svn... and it won't work.
Now read ~/tmp/psptoolchain/readme-ubuntu.txt. It tells you to make sure you have a series of packages installed; a pity they forgot to add a couple of packages (libmpfr-dev and libgmp3-dev). This is the full, updated list of packages to install:
sudo apt-get install build-essential autoconf automake bison flex \ libncurses5-dev libreadline-dev libusb-dev texinfo libmpfr-dev \ libgmp3-dev
with that and following the remaining instructions in the readme-ubuntu.txt file you should be able to get the toolchain installed in your computer. It will take some time depending on your processor etc, on my powerpc mac it takes a lot of time (in the order of hours), whereas in my brand new ubuntu machine with quad processor it took ~25 minutes, if I remember correctly.
So once it finishes, everything will be installed at /usr/local/pspdev. You might want to create a shortcut to the samples, which are in /usr/local/pspdev/psp/sdk/samples, but have a look at the other folders anyway, since the .h files are in there too and it's good to know what you're dealing with.
And this is entirely optional, but if you want to install SDL and other libraries, the easiest way I found is to use their psplibraries script. It is hosted in the same SVN repository so you just need to check it out:
mkdir ~/tmp/psplibraries cd ~/tmp/psplibraries svn co svn://svn.ps2dev.org/psp/trunk/psplibraries .
Again, there's a readme-ubuntu.txt file; you might need to install libtool as specified there, and after that, simply run the libraries-sudo.sh file and let it work for a while since it needs to grab the sources for the libraries and build them.
Once that is finished too, the libraries will be also ready for your consumption and linkage inside the /usr/local/pspdev folder too, so everything is nice and clean. The guys at pspdev did a good job, kudos to them!