In my mind, one of the greatest benefits of RESTful APIs is the discoverability provided by the URI. To that end, I always prefer to put API version information in the URL itself. This dramatically reduced the amount of go-round between yourself and outside developers when troubleshooting any issues with the API, or their implementation on the client end. If API version is stored in headers, this is less clear and can lead to hidden issues.
Is this truly REST? Enh, you could argue not, that the URI pointing to the resource changes with the version. I find that letting the REST-at-all-costs mentality guide the design of my APIs only hinders the usability. Very few people actually design fully REST-compliant software, so we're all trying to find out which deviations improve upon the pattern in the real world. Mandatory versions in the URL, in my opinion, is one of the better deviations to make.
As always when discussion REST API design, I must plug this short and easy to read PDF by Apigee: pages.apigee.com/rs/apigee/images/api-design-eboo…. This is some of the best advice you'll get on the subject, and it only takes about 30 minutes to read.