PHP5.5.0から従来のmysql(mysql_connect, mysql_queryなど)拡張モジュールが非推奨になり、将来的に削除される予定になっています。
代わりにmysqliかPDO_MySQLのどちらかを使う事が推奨されています。

mysql拡張モジュールが削除される将来がいつなのかは分かりませんが、既に非推奨となっているのである日突然「mysqlが使えない!」とならないように新規開発の際には乗り換えるべきでしょう。

それぞれの機能比較表が出ていますので下の表をご覧ください。

  ext/mysqli PDO_MySQL ext/mysql
どのバージョンの PHP から使えるか 5.0 5.1 2.0
PHP 5.x に同梱されているか Yes Yes Yes
開発状況 進行中 進行中 保守対応のみ
ライフサイクル 活動中 活動中 非推奨
新規開発でおすすめできるか 活動中 活動中 非推奨
オブジェクト指向のインターフェイス Yes Yes No
手続き型のインターフェイス Yes No Yes
mysqlnd によるノンブロッキングな非同期クエリ Yes No No
持続的接続 Yes Yes Yes
文字セット Yes Yes Yes
サーバーサイドのプリペアドステートメント Yes Yes No
クライアントサイドのプリペアドステートメント No Yes No
ストアドプロシージャ Yes Yes No
複数ステートメント Yes Most No
トランザクション Yes Yes No
SQL によるトランザクション制御 Yes Yes Yes
MySQL 5.1+ の全機能への対応 Yes Most No

どちらか一方を強く推奨している訳ではないので、好みや必要に応じて使い分けるのが良いのではないでしょうか。
mysql拡張モジュールが手続き型だったので同じ感覚で使いたい方や、過去にmysql拡張モジュールで開発を行ったコードを新しい環境に移す時などにはmysqliが良いと思います。

以下、3種類のMySQL用APIの使用例です。

// mysqli(オブジェクト型)
$mysqli = new mysqli("example.com", "user", "password", "database");
$result = $mysqli->query("SELECT 'Hello, dear MySQL user!' AS _message FROM DUAL");
$row = $result->fetch_assoc();
echo htmlentities($row['_message']);

//mysqli(手続き型)
$mysqli = mysqli_connect("example.com", "user", "password", "database");
$result = mysqli_query("SELECT 'Hello, dear MySQL user!' AS _message FROM DUAL");
$row = mysqli_fetch_assoc($result);
echo htmlentities($row['_message']);

// PDO
$pdo = new PDO('mysql:host=example.com;dbname=database', 'user', 'password');
$statement = $pdo->query("SELECT 'Hello, dear MySQL user!' AS _message FROM DUAL");
$row = $statement->fetch(PDO::FETCH_ASSOC);
echo htmlentities($row['_message']);

// mysql
$c = mysql_connect("example.com", "user", "password");
mysql_select_db("database");
$result = mysql_query("SELECT 'Hello, dear MySQL user!' AS _message FROM DUAL");
$row = mysql_fetch_assoc($result);
echo htmlentities($row['_message']);

PHPマニュアルにクラスの一覧や使い方などがありますので、どちらのAPIについても一度目を通しておく事をオススメします。

mysqli
http://php.net/manual/ja/book.mysqli.php

PDO
http://php.net/manual/ja/book.pdo.php