ya eso me suena a js + ajax..
aunque aun no se la logica de tu formulario.
si redirecciona a otra pagina o no, de ser así, puedes pasar por get el mensaje y ya en la pagina destino haces algo así
<div class="mi clase"><?php echo $_GET['mensaje']; ?></div>