La solution la plus simple consiste à itérer, au sens propre par List.iter, un affichage un peu brut des monômes.

open Printf (* Pour écrire « printf » directement *)

let afficher_monome {coeff=c ; degre=d} =
  if c > 0 then printf "+" ;
  printf "%dX^%d" c d

let afficher p = match p with
| [] -> printf "0" (* un cas particulier, quand même *)
| _  -> List.iter afficher_monome p

On notera que les champs de l'enregistrement sont accédés directement par filtrage. Le code est simple, mais au final l'impression n'est pas très belle.

Afficher les listes est toujours un peu embêtant, car on veut un séparateur entre les éléments de la liste. Cela conduit à particulariser le premier (ou le dernier) élément de la liste. Ici c'est encore pire, car le séparateur est le signe du coefficient.

Commençons par perfectionner l'affichage des monômes.

(* fst indique le premier monôme (ne pas afficher le «+») *)
let afficher_coeff fst c =
  if c > 0 && not fst then
    printf "+%d" c
  else
    printf "%d" c

and afficher_puiss d = match d with
| 1 -> printf "X"
| _ -> printf "X^%d" d

let afficher_monome fst m = match m with
| {degre=0} -> afficher_coeff fst m.coeff
| {coeff=1} ->
    if not fst then printf "+" ; afficher_puiss m.degre
| {coeff= -1} ->
    printf "-" ; afficher_puiss m.degre
| _ ->
    afficher_coeff fst m.coeff ; afficher_puiss m.degre

Reste à itérer pour les polynômes.

let afficher p = match p with
| []     -> printf "0"
| m::rem ->
    afficher_monome true m ;
    List.iter (afficher_monmome false) rem

On peut aussi éviter List.iter en écrivant :

let rec do_afficher fst p = match p with
| [] -> ()
| m::rem ->
    afficher_monome fst m ; do_afficher false rem

let afficher p = match p with
| [] -> printf "0"
| _  -> do_afficher true p

Cela revient un peu à écrire List.iter soi-même.