I've found several good tutorials describing two-way SSL authentication for external REST services:
http://wiki.developerforce.com/page/Making_Authenticated_Web_Service_Callouts_Using_Two-Way_SSL
http://www.salesforce.com/us/developer/docs/apexcode/Content/apex_callouts_client_certs_http.htm

These seem to indicate that the process is repreated for each org that wants to use two-way SSL.  Is it possible to develop a app (managed package) which supports two-way SSL without additional configuration required by the installer?

The goal is not to authenticate individual client orgs.  The goal is to simply verify that requests reaching my REST server originated from Salesforce.com.

To elaborate, the goal is to publish on the AppExchange, and allow customers to install the SF app and immediately access an external REST service over two-way SSL without any configuration by the customer.

Thanks,

Andreas