Use both. In fact refer a guide like the OWASP XSS Prevention cheat sheet, on the possible cases for usage of output encoding and input validation.
Input validation helps when you cannot rely on output encoding in certain cases. For instance, you're better off validating inputs appearing in URLs rather than encoding the URLs themselves (Apache will not serve a URL that is url-encoded). Or for that matter, validate inputs that appear in JavaScript expressions.
Ultimately, a simple thumb rule will help - if you do not trust user input enough or if you suspect that certain sources can result in XSS attacks despite output encoding, validate it against a whitelist.
Do take a look at the OWASP ESAPI source code on how the output encoders and input validators are written in a security library.