However, the point of single-sign-on is to allow a second application (in this case, us) to effectively "automatically log the user in" based on trusting a primary application (in this case, salesforce) to assert that a user is authenticated as a particular principal.

I don't see how the tokens passed to us allow us to assure that salesforce has authenticated the user indicated in a secure way.  As stated above, we are going to log them in to our application as that user and give them full access to their data - so we have to know that it is really them, as asserted by salesforce, but in an environment where any machine or person can make arbitrary HTTP requests to our site (since we are not deployed behind a proxy at salesforce, etc.).

For a concrete example, imagine that a bank is signing up to become an AppExchange partner.  They will offer account balances and wire transfers as a tab in salesforce.  On their side, they would do some work to associate a salesforce login name (e.g. bob@companyname.com) with a bank account number or social security number.  Obviously, security is critical - when the tab is clicked on and the accounts page is displayed, it better be the current salesforce user's data!

Now, when salesforce's web tab passes the username, session id, and server url to the bank's web site, the bank has to be able to validate these tokens and "trust" that salesforce has securely authenticated the user.  Once it does that, it can then show the data from the external banking system, and allow operations on that data such as wire transfers.  I know of three methods to do this - one is to use private/public keys to encode the tokens - another is to have the second application make a return call to the originator of the tokens (similar to a kerberos model) - and a third is to put the second server behind a proxy at the same site as the first server (which is not feasible in this case).

Given salesforce's approach, what steps should the bank's application take to validate the tokens?  The username is what indicates the account to use.  However, anybody can make an HTTP request and pass a username - so it's not secure to simply check that.  The session id is interesting, but to prove that it is valid you would have to go back to a salesforce server (i.e. the token originator) to validate that is in active session.  What server serves as the token originator - perhaps that is what the server URL parameter is for?  That gave me the idea that you can use the server URL combined with the session id to verify that the session is valid on that salesforce server.  (However, in this case - how do we make sure that the URL isn't pointing to some non-salesforce server designed to provide bogus validation?)  Once we've determined that the session is indeed valid on a salesforce server, we know that there has been an authenticated session.  However, how do we know it is for the user passed on the URL?  Somebody could just as easily authenticate with the SForce API to salesforce.com, get a valid session token and server URL, and then pass that to our application along with a completely different username.