I pulled out my notes from my successful installs of Mambo. Hopefully they'll help.
First thing I did was create a new MySQL database and carefully record, the db name, dbhostname, username, and password. You'll have to wait long enough for it to be created before you can perform the install.
Be sure you've gone into your webpanel and set your domain to run PHP-as-CGI.
Once files were installed in my domain folder, I went through the web browser install script.
According to the pre-install check, the only difference between the recommended and actual environment was that "Register Globals" was on, not off.
Accept the licensing.
Specify MySQL settings. As you said you know, you're not supposed to use localhost. You should enter the db hostname from the database creation (should be in the form of hostname.somedomain.com. Once this is done, Mambo tells you that propagation was a success!
Accept URL and path. Mambo gives you an admin account. You'll want to make sure you write down your login and password.
Once you're done with that, you delete the install directory and have fun getting to know Mambo.
I hope this helps. If it doesn't, let me know.