Note: the indented bits are intended to be copy/pasted. If you don't know your way around a unix system, and on top of that whatever weird design desisions ubuntu has implemented, it's very easy to mess them up.
Kill mysql and start it up in a completely unprivileged mode:
sudo /etc/init.d/mysql stop
sudo mysqld_safe --skip-grant-tables &
Now, mysqld_safe will block input, so you'll need to open a new terminal tab. Then, connect to mysql's meta database that includes auth information:
mysql -uroot mysql
Run these commands in the mysql prompt to set the root's password to 'password':
update user set Password=PASSWORD('password') where user='root';
flush privileges;
exit;
No, kill mysqld:
mysqladmin shutdown -uroot -ppassword
And restart it normally:
sudo /etc/init.d/mysql start