Absolutely no instructions that I've found are complete and correct. Some come close. I'm dong my work on a PC, but the new bandwagon appears to be a tool called EISA from sourceforge
http://sourceforge.net/projects/esia/ But even with this, it's full of nuances that need to be pointed out for ready success.
Regarding Ubuntu, unfortunately, the readily available downloads are for Debian_Squeeze, but really if you're not installing a desktop, being on Debian is about the same as being on Ubuntu, and maybe even a little better since support is always likely to fall into place for Debian before Ubuntu, since Ubuntu's based on Debian. I recommend going this route, because the process appears to be reliable.
I list all the nuances on where I document the process
http://shankserver.org/2010/09/unbrick-sheevaplug/ , but the one big one to call out is ensuring you have a reliable USB flash drive. Specifically, old 512MB ones are where I have had the most success.
Since your question regarded what and where to download, for the process I'm describing, you download EISA from sourceforge (link above), and then Debian_Squeeze from here
http://sourceforge.net/projects/esia/files/distros/Debian_Squeeze_usb_app.tar.bz2/download Unarchive the download, and put the whole Debian_Squeeze directory onto the USB, leave it plugged into your PC (or Linux box), run EISA, connect your SheevaPlug over serial, etc.