Eso se hace con jQuery, mirá en mii perfil, ahí he dejado muchos plugin, en el último post, dejé plugin para formulario, podés usar el de validación. O buscarte algún otro plugin de validación en jQuery.

Ok, ya vi la otra web, fijate en el diseño (ver código fuente) de ese sitio. Encontrarás que primero agregan una librería de jQuery, luego un .js que se llama funciones, ahí está la validación con jQuery (sin usar un plugin), en dicho archivo está:



$(function() { 
    var emailreg = /^([w-.]+@([w-]+.)+[w-]{2,4})?$/;    
    $(".boton").click(function(){  
        $(".error").fadeOut().remove();
        
        if ($(".nombre").val() == "") {  
            $(".nombre").focus().after('<span class="error">Ingrese su nombre</span>');  
            return false;  
        }  
        if ($(".email").val() == "" || !emailreg.test($(".email").val())) {
            $(".email").focus().after('<span class="error">Ingrese un email correcto</span>');  
            return false;  
        }  
        if ($(".asunto").val() == "") {  
            $(".asunto").focus().after('<span class="error">Ingrese un asunto</span>');  
            return false;  
        }  
        if ($(".mensaje").val() == "") {  
            $(".mensaje").focus().after('<span class="error">Ingrese un mensaje</span>');   
            return false;  
        }  
    });  
    $(".nombre, .asunto, .mensaje").bind('blur keyup', function(){  
        if ($(this).val() != "") {              
            $('.error').fadeOut();
            return false;  
        }  
    });    
    $(".email").bind('blur keyup', function(){  
        if ($(".email").val() != "" && emailreg.test($(".email").val())) {    
            $('.error').fadeOut();  
            return false;  
        }  
    });
});


Estoy elaborando un ejemplo bastante completo, donde planteo el uso de ABC (Altas, Bajas y Cambios) sobre una tabla MySQL, usando php, ajax y jQuery.