Primero de todo mirate esta pagina:
http://www.webtaller.com/manual-php/conexion_mysql.php
Aqui te explican lo basico de mysql + php.
Código PHP:
mysql_connect("host","usuario","password"); //te conectas a tu host donde esta la bd
mysql_select_db("base de datos",conexion); //te conectas a la bd que elijas
mysql_query("consulta",conexion);//haces la consulta que quieras a la bd
Lo que hace la gente es hacer la conexion y la eleccion de la bd en un fichero, que lo llaman conexion.php. Asi para luego siempre que quieran conectarse a la bd llamar a ese fichero, asi es mas sencillo.
El primer paso es crear tu bd en tu host, y despues haz pruebas con un fichero simple para ver si te conectas correctamente.
No soy muy bueno explicando esto, pero hago lo que puedo
Tambien te puede ayudar echar un vistazo a esta pagina:
http://www.programacion.com/php/articulo/php_mysql/