Taken from http://dev.mysql.com/doc/refman/5.0/en/resetting-permissions.html

Stop mysqld and restart it with the –skip-grant-tables option. This enables anyone to connect without a password and with all privileges. Because this is insecure, you might want to use –skip-grant-tables in conjunction with –skip-networking to prevent remote clients from connecting.

mysql_safe --skip-grant-tables --skip-networking

Connect to the mysqld server with mysql

Issue the following statements in the mysql client. Replace the password with the password that you want to use.

UPDATE mysql.user SET Password=PASSWORD('MyNewPass') WHERE User='root';
FLUSH PRIVILEGES;

The FLUSH statement tells the server to reload the grant tables into memory so that it notices the password change.

Be careful in the instance that the mysql.user table is mysteriously empty, as mysql_secure_installation will remove any non-localhost entries. This is normally caused by a bad DB install. The easiest solution if you have no data is to (re)move your data directory, and install a fresh copy of the DB.

mv /var/lib/mysql /root/ 
mysql_install_db --datadir=/var/lib/mysql --user=mysql

Note the second parameter is important. You can then run mysql_secure_installation to set a password etc