Standard pHp and js: have onblur event submit the form to your form handler script, it checks the entry vs. your db and returns a msg to the form page (OK or Not). This is very heavy on resources because your WHOLE page needs to be reloaded and usually the whole form data will be processed, so it could be awkward to separate a simple name query (onblur) from a "proper" submission (submit button).
The Ajax version:
onblur will call a js script to send and retrieve data from a very simple php file that can access your db. This is relatively painless and easy to isolate from a "proper" submit button action. If you're concerned about the complexity of Ajax - don't be. The prototype library (http://www.prototypejs.org) takes care of the ajax objects. Nice and simple.