RESTful thoughts - versioning

I've done a lot of thinking on versioning for an API I've been working on. I feel that the mystical nature of API versions should not be the last consideration of an API implementation - why do that to yourself; why do that to your customers?

So how does one approach versioning for the "Programmable Web?" What do your users do when they come to a fork in road?

Approach it using basic considerations of any API architecture (not holding true to Zachman's approach - we'll handle the where, when, and why some other day)

Who - always consider the consumer. I would consider myself a clown if I didn't listen to the users of the API. Beyond patterns, best practices, and textbook principles - the user has perspective that exists outside of any "should be" reality. They understand the serendipitous side of your API so-to-speak. Side note: This consideration goes way beyond versioning and down to the deep roots of the API's foundation.
How - What are the options. If I have half a dozen choices, what are some proven patterns, what is the industry moving on? For instance, authentication for an API - let's say you have an API that will be used by open-source consumers for social mashups that share resources. The seemingly obvious option would be OAUTH. You don't eat soup with a fork (unless you're eating a soup sandwich) - why should you skip thinking about the appropriate use of technology for an API
What - Typically if it is a web-based API, you'll be dealing with resources - especially when you're dealing with an API based on RESTful principles. What type of payloads are you dealing with? Are you going to implement resource extensions (.json, .xml, etc...)?

What are the options:

URIs
Custom Headers
By way of HATEOAS (Hypermedia as the engine of application state - one of the basic proposed constraints of REST, or some other resource driven-hypermedia makeup)
Request definition
etc...

URIs http://api.mysite.com/v2/people/1 <- like http: api2.mysite.com people 1<- not a fan Custom Headers


Request.Headers.Add("X_HTTP_MYAPI_VERSION","2.0")

<- though explicit, less visible, would be buried in code HATEOAS While, by default the HATEOAS principles are built-in to a RESTful API - think of it like a page on a website and the context of that page tells what can be edited, created, viewed, who you are, etc...

So, in REST one of the parts of this principle is how your application will interpret n * document representations / formats that you API supports.

For instance, I could create a document representation with versioning for People information coming out of my API in an XML format: application/MyAPI-person-v3+xml

I understand the RESTful approach to explicitly seek a resource, it still feels like it is breaking some low level HTTP rule - my take, HTTP has worked this long for a reason, I don't feel very comfortable making up content types for a versioning implementation.

But... media-types seem to be a good option because we are dealing specific resources with specific implementations.

Request Definition
Probably my least favorite. Basically, you put all information about the resource in the parameters (NOT the header) of the request. This approach pretty much does the same thing as the other options, except, makes it more difficult for the programmer to implement. This pattern is commonly used on pin-point APIs where there is only one interface to consume - basically 1 URI for multiple resources - RESTifarians, please don't get upset at me for even mentioning this as an option for RESTful versioning.

So to the RESTful "Who" out there - what are your thoughts on a versioning pattern?