As others have said, you should do both. Here's why:
Client Side
You want to validate input on the client side first because you can give better feedback to the average user. For example, if they enter an invalid email address and move to the next field, you can show an error message immediately. That way the user can correct every field before they submit the form.
If you only validate on the server, they have to submit the form, get an error message, and try to hunt down the problem.
(This pain can be eased by having the server re-render the form with the user's original input filled in, but client-side validation is still faster.)
Server Side
You want to validate on the server side because you can protect against the malicious user, who can easily bypass your JavaScript and submit dangerous input to the server.
It is very dangerous to trust your UI. Not only can they abuse your UI, but they may not be using your UI at all, or even a browser. What if the user manually edits the URL, or runs their own Javascript, or tweaks their HTTP requests with another tool? What if they send custom HTTP requests from curl or from a script, for example?
(This is not theoretical; eg, I worked on a travel search engine that re-submitted the user's search to many partner airlines, bus companies, etc, by sending POST requests as if the user had filled each company's search form, then gathered and sorted all the results. Those companies' form JS was never executed, and it was crucial for us that they provide error messages in the returned HTML. Of course, an API would have been nice, but this was what we had to do.)
Not allowing for that is not only naive from a security standpoint, but also non-standard: a client should be allowed to send HTTP by whatever means they wish, and you should respond correctly. That includes validation.
Server side validation is also important for compatibility - not all users, even if they're using a browser, will have JavaScript enabled.
Addendum - December 2016
There are some validations that can't even be properly done in server-side application code, and are utterly impossible in client-side code, because they depend on the current state of the database. For example, "nobody else has registered that username", or "the blog post you're commenting on still exists", or "no existing reservation overlaps the dates you requested", or "your account balance still has enough to cover that purchase." Only the database can reliably validate data which depends on related data. Developers regularly screw this up, but PostgreSQL provides some good solutions.
