Puedes hacerlo en php o en javascript, segun lo elaborado que lo quieras.
Algo facil en javascript seria colocar este codigo dentro de la etiquetas<head>y</head>:   
Código HTML:
Ver original- <script language="JavaScript"> 
- var Frase=new Array()  
- Frase[0] = "frase 1"; 
- Frase[1] = "frase 2"; 
- Frase[2] = "frase 3"; 
- Frase[3] = "frase 4"; 
- Frase[4] = "frase 5"; 
- Frase[5] = "frase 6"; 
-   
- var F = Frase.length; 
- var aleatorio=Math.round(Math.random()*(F-1)); 
- function fraseAleatoria(){ 
-         document.write(Frase[aleatorio]); 
- } 
Luego coloca el siguiente codigo donde quieras que aparezca la frase:   
Pero ten en cuenta que el ususario puede tener javascript deshabilitado, por ello recomiendo php.
Espero haberte ayudado.