A server using HSTS sends a HTTP header (Strict-Transport-Security), and a time for which this header is valid (similar to a cache max-age attribute). Within that time, requests to the server should use https automatically, and not connect to the http version first and get a redirect to the https site. Second, it will turn all insecure links to secure links. Third, a user-agent complying to HSTS will not allow the user to proceed loading a web site upon SSL errors (e.g. certificate expired).
E.g. paypal.com is already supporting this, so are Google Chrome and Firefox in recent versions.