At first I thought running ubuntu on my phone would require blowing away the android OS, but that's not the case. Instead, an ubuntu filesystem gets mounted on the SD card, with all the system files set up right so that things like apt-get work. Some things don't work, I think because the android kernel isn't quite what the ubuntu apps expect, but you know you're doing well when firefox runs!
The nexusonehacks Ubuntu disk image worked great for me, but took forever to download and had a ton of stuff that I didn't need, like firefox and openoffice.org.
So I stripped it down to bare bones and upgraded it to lucid. Check it out: run a bare-bones Ubuntu Lucid filesystem alongside android on a froyo phone.