il punto è:

Hai già usato ajax?
Hai una libreria che preferisci?

Dopodichè come ti diceva Manuelandro, basta mettere nella pagian sul server una query che restituisca 1 o 0 a seconda se lo username esiste già o meno, dopodichè nella funzione javascript di callback di ajax metti un alert, oppure popoli un div con il messaggio che vuoi.

ciao