How to use OpenID in RESTful API?

I've now spent some time researching the options and would like to summarize the findings. First, a little bit more context -- I develop and control both the service and API consumer. Consumer is Flash-based app that is served from the same host the API is now and is supposed to be used in browser. No third party clients in sight yet.

So the question can be divided in two parts,

• how do I do the OpenID authentication via API
• how do I maintain the "authenticated" state in subsequent requests

For first part, OpenID authentication almost always includes interactive steps. During the authentication process there will most likely be a step where user is in OpenID provider's web page, signing in and pressing some "I agree" button. So API cannot and shouldn't handle this transparently (no "tell me your OpenID provider and password and I'll do the rest"). Best it can do is pass forth and back HTTP links that client has to open and follow instructions.

Maintaining "authenticated" state

REST APIs should be stateless, each request should include all the information needed to handle it, right? It wouldn't make any sense to authenticate against OpenID provider for each request, so some kind of session is neccessary. Some of the options for communicating session key (or "access token" or username/password) are:

• HTTPS + BASIC authentication ("Authorization: Basic ..." header in each request)
• Signing requests Amazon-style ("Authorization: AWS ... " header in each request)
• OAuth: acquire Access Token, include that and a bunch of other parameters in each request
• Cookie that stores session key ("Cookie: ... " header in each request)
• Signed cookie that stores session information in the cookie itself

There's j