Ну вообще-то это не так сложно. Всё, что нужно знать:

Хост - адрес сервера баз данных mysql
Имя базы данных
Имя пользователя
Пароль - пароль для доступа к БД
Некоторые sql команды
Далее я буду предполагать, что у вас уже заведена база данных на сервере хостера или на домашнем компьютере
(mysql можно скачать с сайта http://mysql.com).

Итак, алгоритм такой:

Устанавливаем соединение с сервером
Выбираем нужную базу данных
Делаем запрос к серверу баз данных (sql запрос)
Обрабатываем результат запроса, если это необходимо
Закрываем соединение (отключаемся от сервера БД)
По части php, чтобы работать с БД надо знать несколько функций (полный список смотри в php мануале).

mysql_connect();
mysql_select_db();
mysql_query();
mysql_fetch_array();
mysql_close();
Это тот минимум, который позволит вам устанавливать соединение с сервером mysql,
выбирать базы данных и делать запросы к серверу баз данных.

Для справки!
Все php функции которые предназначены для работы с базой данных mysql имеют префикс mysql_
Я не буду рассматривать синтаксис каждой функции. Надеюсь у вас есть php manual
(его можно скачать с сайта http://php.net). Рассмотрим эти функции в деле т.е. на примере.

Допустим в нашей базе данных храниться одна таблица со следующей структурой:

имя поля тип(длина) описание
id целый(2) уникальный номер
name символьный(100) имя
tel символьный(20) телефон

Таблица имеет имя: customer, а наша база данных называется database.

Допустим, что ваши данные для подключения к серверу mysql Такие:

Хост: localhost
Имя пользователя: guest
Пароль: mypassword
Для начала необходимо создать нашу таблицу customer. Напишем скрипт который создаст в базе данных database
таблицу customer. Назовём файлик как install.php.

Файл install.php

<?php

// Данные для mysql сервера
$dbhost = "localhost"; // Хост
$dbuser = "guest"; // Имя пользователя
$dbpassword = "mypassword"; // Пароль
$dbname = "database"; // Имя базы данных

// Подключаемся к mysql серверу
$link = mysql_connect($dbhost, $dbuser, $dbpassword);

// Выбираем нашу базу данных
mysql_select_db($dbname, $link);

// Создаём таблицу customer
// т.е. делаем sql запрос
$query = "create table customer (id int(2) primary key
auto_increment, name varchar(100), tel varchar(20))";
mysql_query($query, $link);

// Закрываем соединение
mysql_close($link)

?>
Функция mysql_connect() возвращает идентификатор соединения. Этот идентификатор необходимо
указывать во всех mysql функциях. Можно провести аналогию с указателем на файл (file pointer),
который используется функциями по работе с файлами. В параметрах функции мы указали хост,
имя пользователя и пароль к базе данных.

На сервере mysql храниться не только ваша база данных. Сервер может обслуживать тысячи таких баз данных.
Поэтому, чтобы получить доступ к своей базе данных, необходимо выбрать её.
Выбор базы данных осуществляется функцией mysql_select_db(). В параметрах указывается:
имя требуемой базы данных $dbname и идентификатор соединения $link, который мы
получили с помощью функции mysql_connect().

После того как мы подключились к серверу mysql и выбрали нашу базу данных, мы делаем sql запрос.
Литературу по языку sql вы найдёте на сайте mysql.ru. В запросе указываем, что мы хотим создать
таблицу с именем customer и со структурой приведённой в таблице выше. Запрос к серверу mysql
осуществляется с помощью функции mysql_query(). В параметрах указывается сам запрос $query и идентификатор соединения $link.

И, наконец, отключаемся от сервера (закрываем соединение) функцией mysql_close().
В параметрах указываем идентификатор того соединения, которое нужно закрыть.

Для справки!
На самом деле скрипт может устанавливать несколько соединений с сервером mysql.
Всё зависит от хостинга на котором вы сидите.
Если вы всё сделали правильно, то на сервере mysql в вашей базе данных, появится таблица customer.

После того как мы создали таблицу, её надо заполнить т.е. записать в нёё какие-нибудь данные (записи).
Напишем скрипт, который будет добавлять запись в нашу таблицу. Назовём файл скрипта как insert.php.

Файл insert.php

<?php

// Данные для mysql сервера
$dbhost = "localhost"; // Хост
$dbuser = "guest"; // Имя пользователя
$dbpassword = "mypassword"; // Пароль
$dbname = "database"; // Имя базы данных

// Подключаемся к mysql серверу
$link = mysql_connect($dbhost, $dbuser, $dbpassword);

// Выбираем нашу базу данных
mysql_select_db($dbname, $link);

// Добавляем запись в нашу таблицу customer
// т.е. делаем sql запрос
$query = "insert into customer values(0,'Иванов Иван Иванович',
'(095) 555-55-55')";

mysql_query($query, $link);

// Закрываем соединение
mysql_close($link);

?>
Посмотрев этот скрипт вы заметете, что он отличается от предыдущего только строкой запроса $query.

Теперь когда мы умеем записывать данные в базу данных, перейдём к процедуре запроса данных из базы mysql.
Для этого напишем скрипт и назовём файлик select.php.

Файл select.php

<?php

// Данные для mysql сервера
$dbhost = "localhost"; // Хост
$dbuser = "guest"; // Имя пользователя
$dbpassword = "mypassword"; // Пароль
$dbname = "database"; // Имя базы данных

// Подключаемся к mysql серверу
$link = mysql_connect($dbhost, $dbuser, $dbpassword);

// Выбираем нашу базу данных
mysql_select_db($dbname, $link);

// Добавляем запись в нашу таблицу customer
// т.е. делаем sql запрос
$query = "select * from customer";

// Запрашиваем
$result = mysql_query($query, $link);

while($rows = mysql_fetch_array($result, mysql_assoc))
{
printf("id:%d, name:%s, tel:%s",
rows['id'],rows['name'],rows['tel']);
}

// Закрываем соединение
mysql_close($link);

?>
Ну тут... всё понятно :) :) :) Естественно изменилась строка запроса $query,
которая теперь содержит sql-оператор select. Так же добавился небольшой код while() { .... }.
Скажу только, что функция mysql_fetch_array() обрабатывает результат запроса и возвращает
массив полей текущей! Внимание! текущей строки результата.

Константа mysql_assoc указывает на то, что функция должна вернуть ассоциативный массив полей.
После того как функция mysql_fetch_array() обработает все строки результата, она вернёт значение
false и тогда цикл while() - не выполниться.

Тут в цикле используем функцию printf(). Она очень похожа на эту же функцию в языке c.
Справку по функции printf() можете посмотреть в php мануале.

Надеюсь моя статья хоть немного помогла вам понять связь php и mysql.