Beh..... il codice è piuttosto leggibile.
Cos'è che non capisci???

L'unica cosa che vedo omessa è la provenienza di $start.
Suppongo provenga dall'URL della pagina, ma quello glielo devi dire te: in fondo alla pagina devi semplicemente mettere i link Avanti e Indietro.

Ti scrivo il codice, un po' migliorato e commentato.
Codice PHP:
<?php
// richiamo le variabili di accesso al DB
include("config.php"); 

// connessione al DB
$db = mysql_connect($db_host, $db_user, $db_password) OR die ("Errore nella connessione."); 

// seleziono il DB
mysql_select_db($db_name, $db) or die ("Errore nella selezione del database."); 

// recupero la variabile passata dalla url che indica a che pagina siamo
$pag = $_GET['pag'];
 

if (!isset($pag) OR $pag <= 1) {
// se la variabile start non è assegnata, è perché sto aprendo la pagina 1
// per cui stampo i primi 20 record presenti nel DB
$start= 0; 
$step = 20;
} else {
// se start è dichiarata vuol dire che almeno i primi 20 record
// li ho già visualizzati, per cui devo scattare ai 20 successivi
$start = $pag * 20;
$step = $start + 20;
}
$query = "SELECT id,titolo,artista,data,prezzo FROM catalogo ORDER BY titolo DESC LIMIT $start,$step"; 
$result = mysql_query($query, $db); 
while ($row = mysql_fetch_array($result)) 
{ 
echo $row[artista]." - ".$row[titolo]; 
} 

// compongo il menu di navigazione tra le pagine
$prima = $pag - 1;
$dopo = $pag + 1;

// il menu avrà il bottone INDIETRO solo se mi trovo 
// nella pagina 2 o successiva
if ($pag >= 2) {
$navigazione .= "
<a href=\"?pag=$prima\">Indietro</a>
";
}

$navigazione .= "
<a href=\"?pag=$dopo\">Avanti</a>
";

echo "<hr />".$navigazione;

mysql_close($db); 
?>
Come puoi notare, la pagina richiama sempre se stessa associando solo la variabile pag per indicare allo script quanti record sono stati visualizzati.
Codice PHP:
$navigazione .= "
<a href=\"?pag=$xxx\">xxx</a>
"; 
Ti manca solo di aggiungere un controllo per far capire allo script di non stampare il bottone Avanti nel caso tu sia arrivato all'ultimo record.