thorpe pretty much sums it up: use both. Using Javascript to check what can be checked clientside is much faster and lightens load on your server. And for those who can't or won't or avoid Javascript validation, use PHP to check everything again.
I don't know about Ajax being an alternative: it still requires Javascript 🙂 as well as client-server interaction - kinda the worst of both worlds when it comes to form validation.